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

Question

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

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

好吧,第一个循环显然是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乘以谐波系列的总和,它没有很好的闭合形式表示.但如在这里它是O(log(n)).总的来说算法是O(n log(n))

Answer 3

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

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

我们在哪里,通过相关积分(ii)逼近n:和谐数.因此,您的算法以O(n·ln(n))渐近的方式运行.

离开渐近行为并研究算法的实际增长,我们可以使用@chux 的精确(n,cnt)(cnt内部迭代次数)对的好样本数据(参考他的答案),并与上面估计的迭代次数进行比较,即,n(1+ln(n))-ln(n).显而易见的是,估计与实际计数整齐地协调,请参见下面的图表或实际数字的此片段.

最后请注意,如果我们让上面n->?的总和1/i,所得到的系列是无限谐波系列,奇怪的是,它是发散的.对后者的证明利用了这样一个事实,即无限和非零项本身自然是无限的.然而,在实践中,对于足够大但不是无穷大的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