循环的 O 符号

Question

for(int i = 0; i < n; i++) {
   for(int j = 0; j < i; j++) { 
      O(1);
   }
}

这里的func是n * (n+1) / 2但是如果outerloop条件是i < log(n)呢？我对相互关联的循环有疑问。

Answer 1

你只需要计算迭代的总数：

1 + 2 + 3 + .. + n - 1 = n * (n - 1) / 2

正如您正确推断的那样。当您将 n 替换为 log(n) 时，只需在最终公式中执行相同的操作，然后变为 log(n) * (log(n)+1) / 2，或者在大 O 表示法中，O((log(n))^2).

Answer 2

如果外循环的条件变为i < log(n)，则嵌套双循环结构的整体复杂度从 O(n²) 变为 O (log(n)²)

您可以用一个简单的替换 k = log(n) 来证明这一点，因为根据 k 的循环复杂度是 O(k²)。反转替换产生 O(log(n)²).

Answer 3

对于嵌套 for 循环（当使用 O 表示法时，ofc），您可以乘以所有循环的最坏情况。如果第一个循环转到 x 并且您有一个嵌套循环转到 i（i 在最坏情况下为 x），那么您的运行时间复杂度为 O(x^2)

O notation of a Loop