我的function的时间复杂度是多less？
开始研究复杂性，我正在努力这个：
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 。 我有这个对吗？
编辑:(不是重复的）我知道什么大O。 我已经在特定的情况下提出了正确的评估。
外循环运行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）），如你所料。
第一个内部循环运行n次
第二个内部循环运行n/2次
第三个内部循环运行n/3次
最后一个运行一次
所以n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n)
这是n乘以谐波序列的总和，它没有一个很好的封闭forms表示。 但是如这里所示，它是O(log(n)) 。 所以整体algorithm是O(n log(n))
作为替代，使用variablesreplacey = n - x然后使用Sigma符号来分析algorithm内部while循环的迭代次数。
上面高估了，对于每个内部while循环，在n-1不是i的倍数的情况下，即(n-1) % i != 0情况下，迭代次数为1 。 当我们继续时，我们假设(n-1)/i是(n-1)/i的所有值的整数，因此高估了内部while循环中的迭代总数，随后在(i)下面包括较小或相等的符号。 我们继续进行Sigma符号分析：
我们在(ii)中已经用相关积分近似了n次谐波数 。 因此，你的algorithm在O(n·ln(n))中渐近地运行。
离开渐近行为并研究algorithm的实际增长，我们可以用@chux（参考他的回答）使用精确的(n,cnt) （其中cnt是内部迭代次数）对的好样本数据，并且与估计从上面的迭代次数，即n(1+ln(n))-ln(n) 。 很明显，这个估计和实际数量整齐地协调一致，看下面的图或者这个片段为实际的数字 。
最后要注意的是，如果在1/i以上的总和中令n->∞ ，那么所得到的序列就是无限谐波序列 ，这个序列好奇地发散了。 后者的certificate利用了这样一个事实，即在无限项的无限和中自然是无限的。 然而，在实践中，对于一个足够大但不是无穷的n ， ln(n)是总和的一个适当的近似值，这个差异与我们这里的渐近分析无关。
试图通过testing和graphics。 log2 vs log2图看起来相当线性。 大于线性O（n）且小于O（n * log（n））之间的东西。 “画”你自己的结论。
[编辑]
使用math派生的公式，计算的O（）是O（n * log（n））的上界。 例如，当n是6时，迭代计数是6 + 3 + 2 + 1.5 + 1.2 + 1 = 14.7个循环，而不是实际的6 + 3 + 2 + 2 + 2 + 1 = 16。随着n增加，这个差别相对较小，因此略小于O（n * log（n））的增长。 所以通过不忽略代码使用整数math，我们有一个更具挑战性的问题。
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
