我的功能的时间复杂度是多少？ [重复]

Question

这个问题在这里已有答案：

• How to find time complexity of an algorithm 9个答案
• Big O, how do you calculate/approximate it? 23回答
• Finding Big O of the Harmonic Series 2回答

开始研究复杂性，我正在努力解决这个问题：

void what(int n) {
    int i;
    for (i = 1; i <= n; i++) {
        int x = n;
        while (x > 0)
            x -= i;
    }
}

好吧，第一个for循环显然是O(n)。第一次迭代是O(n)，第二次是O(n/2) ..和我猜的那样log(n)次？这意味着O(n) * O(log(n)) = O(n * log(n)) complexity。我做对了吗？

编辑:(不是重复）我知道Big O是什么。我已经在特定情况下询问了正确的评估。

Answer 1

外环运行n次。

对于每次迭代，内部循环运行n / i次。

总运行次数是：

n + n/2 + n/3 + ... + n/n

渐近（忽略整数运算舍入），这简化为

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

这一系列松散地汇聚于n * log(n)。

因此，复杂度是O（N.log（N）），正如您所期望的那样。

Answer 2

第一个内循环运行n次 第二个内循环运行n/2次 第三个内循环运行n/3次 ..最后一次运行一次

所以n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n)。

这是n乘以谐波系列的总和，它没有很好的闭合形式表示。但如图所示，here是O(log(n))。总的来说算法是O(n log(n))

Answer 3

作为替代方案，使用变量替换y = n - x，然后使用Sigma表示法来分析算法的内部while循环的迭代次数。

对于1不是n-1的倍数，即i的情况，上面过高估计了每个内部while循环，(n-1) % i != 0的迭代次数。当我们继续时，我们假设(n-1)/i是i的所有值的整数，因此高估了内部while循环中的迭代总数，随后包括下面(i)处的小于或等于符号。我们继续进行Sigma符号分析：

在(ii)，我们在哪里接近n：harmonic number由相关的积分。因此，您的算法在O(n·ln(n))中渐近运行。

---

离开渐近行为并研究算法的实际增长，我们可以使用精确的(n,cnt)（其中cnt是内迭代的数量）对的良好样本数据@chux（参考他的答案），并与估计的迭代次数进行比较以上，即n(1+ln(n))-ln(n)。很明显，估计与实际计数完全一致，见下图或this snippet for the actual numbers。

---

最后请注意，如果我们让n->∞在1/i上面的总和，那么最终的系列就是infinite harmonic series，奇怪的是，它是分歧的。对后者的证明利用了这样一个事实，即无限和非零项本身自然是无限的。然而，在实践中，对于足够大但不是无穷大的n，ln(n)是和的适当近似，并且这种分歧与我们的渐近分析无关。

---

Answer 4

通过测试和图形尝试这一点。 log2 vs log2图看起来相当线性。介于大于线性O（n）和小于O（n * log（n））之间的东西。 “画出”你自己的结论。

[编辑]

使用数学推导公式，计算的O（）是O（n * log（n））的上限。这使用“循环迭代的分数”，将计数增加一小部分，而不是1。当n为6时，迭代计数为6 + 3 + 2 + 1.5 + 1.2 + 1 = 14.7循环而不是实际6 + 3 + 2 + 2 + 2 + 1 = 16.当n增加时，这种差异相对较小，因此略小于O（n * log（n））的增长。因此，通过不忽略代码使用整数数学，我们有一个更具挑战性的问题。

---

unsigned long long what(int n) {
  unsigned long long cnt = 0;
  int i;
  for (i = 1; i <= n; i++) {
    int x = n;
    while (x > 0) {
      x -= i;
      cnt++;
    }
  }
  return cnt;
}

void wtest(int n) {
  unsigned long long cnt = what(n);
  printf("%d %llu\n", n, cnt);
  fflush(stdout);
}

void wtests(void) {
  int i = INT_MAX/2 + 1;
  while (i > 0) {
    wtest(i);
    i /= 2;
  }
}

int main(void) {
  wtests();
  return 0;
}

产量

1073741824 23567395117
536870912 11411566988
268435456 5519718329
134217728 2666826555
67108864 1286897093
33554432 620190504
16777216 298466265
8388608 143418602
4194304 68802063
2097152 32947406
1048576 15746897
524288 7510048
262144 3573331
131072 1695816
65536 802493
32768 378537
16384 177921
8192 83286
4096 38803
2048 17973
1024 8275
512 3782
256 1713
128 765
64 337
32 145
16 61
8 24
4 9
2 3
1 1