计算函数的复杂度

Question

我写了一个函数来计算最长递增序列的长度。这里 arr[] 是长度为 n 的数组。而lisarr长度为n，用来存储元素i的长度。

我在计算作为主定理输入的递归表达式时遇到困难。

int findLIS(int n){
        if(n==0)
            return 1 ;
        int res;
        for(int i=0;i<n;i++){
            res=findLIS(i);
            if(arr[n]>arr[i] && res+1>lisarr[n])
                lisarr[n]=res+1;
        }
        return lisarr[n];
    }

请给出递归关系的计算方法。应该是 T(n)=O(n)+T(1)?

Answer 1

是O(2^n)。让我们计算准确的迭代次数并用 f(n) 表示。递归关系是 f(n) = 1 + f(n-1) + f(n-2) + .. + f(1) + f(0)，f(1)=2 和 f(0)=1，得到 f(n)=2*f(n-1)，最后 f(n)=2^n.

归纳证明：

Base n=0 -> 函数只有一次迭代。让我们假设 f(n)=2^n。然后对于输入 n+1 我们有 f(n+1) = 1 + f(n) + f(n-1) + .. + f(1) + f(0) = 1 + (2^n + 2^(n-1) + .. + 2 + 1) = 1 + (2^(n+1) - 1)=2^(n+1).。开头的第一个来自 for 循环之外的部分，总和是 for 循环的结果——你总是对 i 中的每个 i 进行一次递归调用23=].

计算函数的复杂度

Calculating the complexity of the function

recursion

big-o

time-complexity