java - 时间复杂度 - 递归调用

Question

我试图了解如何计算算法的时间复杂度。

我有这段代码：这是整个方法：

public void solve(int i) {
    if(i < 2) {
        return;
    }
    solve(i-1); //recursive call
    int x = v[n-i];
    for(int j = n-i+1; j < n; j++) {
        if(x > v[j]) {
            count++;
        }
    }
    return;
}

我认为复杂度是 O(n)。我对吗？

谢谢

Answer 1

复杂性应该是在最坏的情况下O(N^2)您将进行迭代。N + (N-1) + (N-2) + 1 = N ( N + 1 ) / 2

Answer 2

复杂性是O(i^2)，n这里不管。

该函数将运行i时间（直到i<2）。每次迭代将运行i时间 (n-(n-i+1)=i-1)。

我们可以O(N^2)在N提到 to时调用它i。

笔记！ N和n这里不一样！