运行时间复杂度

Question

我相信下面的代码是n^3的大的theta，这是正确的吗？

for (int i = 0; i < n; i ++) 
{ // A is an array of integers 
    if (A[i] == 0) { 
     for (int j = 0; j <= i; j++) { 
      if (A[i] == 0) { 
      for (int k = 0; k <= j; k++) { 
       A[i] = 1; 
      } 
      } 
     } 
    } 
} 

而且，以下是n日志（n）的大THETA

for (int i = 1; i < n; i *= 2) 
{ 
    func(i); 
} 

void func(int x) { 
    if (x <= 1) return; 
    func(x-1); 
} 

因为for循环会跑的log（n）次，FUNC最多n递归调用运行。

感谢您的帮助！

Answer 1

你的直觉看起来正确。请注意，对于第一位，如果输入包含非零元素，则时间复杂度将下降到big-theta（n）。如果你删除了支票，那肯定会是big-theta（n^3）。

Answer 2

您对第二段代码正确，但第一段不是Big-Theta(n^3)。它甚至不是O(n^3)！关键的观察是：对于每个i，，最内层循环将最多执行一次。

显然，最坏的情况是当数组只包含零时。但是，A[i]将在最内循环的第一遍中设置为1，并且if (A[i] == 0)对于相同的i的所有后续检查将被评估为false，并且直到i增量为止，最内层循环将不再执行。因此，总共有1 + 2 + 3 + .. + n = n * (n + 1)/2次迭代，所以第一个片段的时间复杂度为O(n^2)。

希望这会有所帮助！