python - 确定以下编码段的时间复杂度

Question

如何确定该编码段的时间复杂度？我是 python 新手，非常感谢任何形式的帮助!

sum = 0
i = n
while (i>= 1):
    sum += i
    i /= 2
i = n
j = 2
while (i >= 1):
    sum +=i
    i /= j
    j *= 2

我认为第一个循环可能是 (log n + 2)，第二个循环可能是 (2log n + 4)，但我不确定我是否接近正确的轨道...

Answer 1

就计算复杂度而言，O(n) 指的是实际位长度(他们将 n 称为位长度)。

因此，每次 i 运行第一个循环时，i/= 2 都会移动一位。在第二个循环中，i/= j 移位 1、2、4、8... 位。

记住你有一个名为n的变量，而我谈到的n(输入的位长度)实际上是关于CC理论的约定。

因此，假设您编写的脚本仅包含变量重命名:n 到 m。

sum = 0

i = m
while (i>= 1):
    sum += i
    i /= 2

i = m
j = 2
while (i >= 1):
    sum +=i
    i /= j
    j *= 2

我刚刚重命名了该变量。

现在让我们求和:

第一个循环具有“逐位”复杂度，因此表示法为 O(n)(线性复杂度，每次迭代一位)。

编辑:第二个循环的复杂度如下:“在第K个循环中，它将消耗 1+2+...+2^(k- 1) 位:它将消耗 2^K - 1 位”。

因此，如果第 K 个循环消耗了该数量的位，我们可以说:2^K 位进行 K 次迭代。我们说“对数”:O(log2(n))。

最终结果是:O(log2(n)) + O(n)，它具有线性顺序，因为 n > log(n)。