-2

I am trying to understand how to compute the time complexity of an algorithm .

I have this piece of code: This is the whole method:

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;
}

I think the complexity is O(n). Am I right?

Thanks

4

2 に答える 2

0

複雑さはO(i^2)、nここでは問題ありません。

関数はi回実行されます (までi<2)。各反復はi(n-(n-i+1)=i-1) 回実行されます。

O(N^2)にN言及すると、それを呼び出すことができますi。

ノート！ Nここでは同じではありnません！

于 2013-12-01T12:14:50.233 に答える
0

複雑さは、最悪の場合O(N^2)に反復が発生するようにする必要があります。N + (N-1) + (N-2) + 1 = N ( N + 1 ) / 2

于 2013-12-01T12:03:48.223 に答える