确定这部分代码的时间复杂度

Question

//Assume these 2 arrays were given to us by the user and we don't know 
// its contents
int A[5] = {1,0,2,1,0};   // (1) operation
int y[5] = {0,0,1,1,2};   // (1)

int n = 5; // (1)
for(int i=0; i<n; i++){   // (n) operations
    if(A[i]!= y[i]){      // is this (n) operations in worst case..?
        cout << "hello" << endl; // is this (n) operations in worst case?
    }
 }

我对嵌套语句感到困惑，我们知道 for 循环出现 "n" 次并且与输入大小成正比。但是，在这种情况下，if 语句也与 "n" 成正比吗？ cout语句也是成正比的"n"。这是否意味着这段代码的运行时间为 O(n^3)..？我真的很困惑什么是常量操作，什么不是与输入大小成比例。我假设这里是最坏的情况，没有项目匹配..

Answer 1

您可以这样计算：

for(int i=0; i<n; i++){
    if(A[i]!= y[i]){      
        cout << "hello" << endl
    }
}

你可以说这个 if(A[i]!= y[i]) 是一个复杂度为 O(1) 的操作，在最坏的情况下它将执行 n 次，但每次迭代只执行一次。 cout.

相同

所以你在每次迭代中得到 2 个常量操作。这是

O(n)*(O(1) + O(1)) = O(2*n) = O(n)

确定这部分代码的时间复杂度

Determining the time complexity of this portion of code

big-o