确定代码段的时间复杂度

Question

以下每个代码段的时间复杂度是多少？

1. int i, j, y=0, s=0;
for ( j = 1; j <= n; j ++) 
{
  y=y+j;
}
for ( i = 1; i <= y; i ++) 
{
  s++;
}

我的答案是 O(2n) 因为它在每个循环中迭代 n 次并且有两个循环

2. function (n) {
  while (n > 1) {
  n = n/3 ;
}

我的答案是 n^(1/3) 因为 n 每次都变成其大小的三分之一

3. function (n) {
int i, j, k ;
for ( i = n/2; i <= n; i ++ ) {   //n/2?
  for ( j = 1; j <= n; j = 2*j ) {  //logn
    for ( k = 1; k <= n; k = 2*k ) {  //logn
      cout << ”COSC 2437.201, 301” << endl;
    }
  }
}
}

我说这个问题的答案是 O(log2*log2n*n/2) 但我对第一个 for 循环很困惑。循环只需要迭代 n 次的一半，所以 n/2 正确吗？谢谢大家的帮助。

Answer 1

问题一

第一个循环是 O(n)，因为它运行 n 次。然而，第二个循环执行了 y 次，而不是 n - 所以总运行时间不是“2n”

第一次循环结束时，y的值为：

因此第二个循环占主导地位，因为它是O(n^2)，因此也是整体复杂度。

问题三

这个答案是正确的（但同样，在 O 表示法中删除 2 的因数）。

但是，您必须小心不要天真地将循环的复杂性相乘，因为内循环的边界可能取决于外循环的自发值。

问题二

这是不是O(n^(1/3))！你的推理不正确。

如果你仔细观察这个循环，它实际上类似于问题 3 中内部循环的 reverse:

Q3中k的值从1开始，每次乘以2，直到达到n
Q2中n的值每次除以3，直到达到1。

因此他们都走了 O(log n) 步。

（作为旁注，O(n^(1/3)) 循环看起来像这样:)

for (int i = 1; i*i*i <= n; i++)
   /* ... */

确定代码段的时间复杂度

Determining the time complexity for code segments

c++

algorithm

time-complexity

notation