Python函数时间复杂度检查

Question

嗨，我需要计算这个函数的时间复杂度。 不确定如何确定内部循环的复杂性。可能只是 O(n)，但我认为可能是 O(log(n)，因为循环数量减少（基于 i 的增长，j 在 n 中出现的次数更少）。有帮助吗？

Answer 1

在 for 循环的第一次迭代中，i=1

进入 while 循环：

同时j

我们将 k 定义为该 while 循环的迭代次数。你可以注意到 j = 2*k 当 j >= n，即 2k >= n，即 k >= n/2 时，此 while 循环结束

在第二次迭代时，逻辑相同，但 j = 22k，因此 while 循环运行 n/(2*2) 次。

在第三次迭代时，while 循环运行 n/(2*3) 次

在 for 循环的第 i 次迭代中，while 循环运行 n/(2*i) 次

总之，在复杂度计算中，您可以得到： $$ C = \sum_{i=1}^{n} n/(2*i) $$ $$ C = n/2 * \sum_{i=1}^{n} 1/i $$

1/i 之和的复杂度为 O(ln(n))：https://en.wikipedia.org/wiki/Harmonic_number

因此我想说你的算法的复杂度是 O(n*ln(n))