解析易递归方程

Question

我必须找到以下函数的递归方程。

public static boolean f(int[] a) {
    return fr(a, 0);
}

private static boolean fr(int[] a, int i) {
    int n = a.length;
    if(i >= n-1) 
        return true;
    else if(a[i] > a[i+1]) 
        return false;
    else 
        return fr(a, i+1);
}

我认为是：

T(1) = 1

T(n) = T(n - 1)

解析我得到结果T(n) = n。这是正确的？这个方程式的分辨率似乎很奇怪.. 看代码很容易看出复杂度是Θ(n)（贯穿整个数组）。

这是一个愚蠢的问题，但让我感到困惑。感谢任何想帮助我的人

Answer 1

T(1) = O(1)
T(n) = T(n-1) + O(1)

这确实是顺序搜索的特征，它具有 O(n) 时间复杂度。这是因为 T(n) = T(n-1) 具有 O(n) 复杂度，并且 O(1) 项消失了。

解决方案很简单：假设我们知道 T(n) = T(n-1)，我们也知道 T(1) = O(1)。这意味着 T(2) = O(1) 和 T(3) = O(1) 等等。所以它等同于 n*O(1) 即 O(n).

解析易递归方程

Resolution easy recurrence equation

recurrence

time-complexity