python中特定函数的时间复杂度

Question

嗨，我试图理解为什么下一个函数的时间复杂度：

\n

def f(n):\n    result = 0\n    jump = 1\n    cur = 0\n    while cur < n:\n        result += cur\n        if jump*jump < n:\n            jump *= 2\n        cur += jump\n    return result\n

\n

是 O(\xe2\x88\x9an)。我知道函数内 if 语句下的代码会执行到jump>= \xe2\x88\x9an 为止，我还注意到cur= 1 + 2 + 4 + 8 + 16 + ...但我仍然无法得到回答。

\n

Answer 1

这里需要一点数学知识。

\n

假设迭代后jump^2大于或等于，则不会再次加倍。这里我们有：nmjump

\n

jump = 2^m >= \xe2\x88\x9an\n

\n

此时，cur是：

\n

cur = 1 + 2 + 4 + ... + 2^m = 2 ^ (m + 1) - 1\n

\n

那么，我们的迭代总数不会大于：

\n

          n - (2 ^ (m + 1) - 1)\nm + ceil( --------------------- )\n                  2^m\n

\n

因为我们有2^m >= \xe2\x88\x9an和2 ^ (m - 1) < \xe2\x88\x9an，所以

\n

            n - (2 ^ (m + 1) - 1)\n  m + ceil( --------------------- )\n                    2^m\n                  n - 2\xe2\x88\x9an + 1\n< (log \xe2\x88\x9an + 1) + (----------- + 1)\n      2               \xe2\x88\x9an\n           n + 1\n= log \xe2\x88\x9an + -----\n     2      \xe2\x88\x9an\n

\n

这里，显然(n + 1) / \xe2\x88\x9an是O(\xe2\x88\x9an)，对数也是O(\xe2\x88\x9an)，所以两者之和是O(\xe2\x88\x9an)。

\n

_{因为它涉及时间复杂度，所以我们可以更宽松地证明它。例如，jumpreach之前\xe2\x88\x9an是O(log_2 \xe2\x88\x9an)复杂度，之后是O(\xe2\x88\x9an)复杂度。两者相加显然就是O(\xe2\x88\x9an)复杂性。}

\n