-1

嗨，我需要了解以下算法的时间复杂度。

def complex(n):
    l=[]
    i=1
    while i<n:
        l=list(range(i))
        i*=2

我已经意识到它在循环中运行 int(log(n,2)) 次，但我很难将 range(i) 合并到最终表达式中。任何帮助表示感谢。

4

2 回答 2

3

您已经计算出它运行int(log(n, 2))迭代。（您可以通过在循环中添加一个计数器并使用例如 1、2、4、8、16、32、64 等调用它并看到计数器每次上升 1 来非常容易地测试它n双打。）

现在您想知道循环内部需要多长时间。在这里，您需要知道range和list函数的时间复杂度。我可以给你答案，事实上你可能会猜到它们，但除非你开始阅读 CPython 的源代码，否则你无法真正证明这一点。所以，让我们用一些简单的时间来测试它：

import timeit
for i in range(20):
    n = 1 << i
    t = timeit.timeit(lambda: list(range(n))
    print('{} takes {}'.format(n, t))

如果你运行这个，你会发现，一旦超过 32 倍，加倍n似乎需要加倍的时间。所以，这意味着list(range(n))是 O(n)，对吧？

让我们验证这是否有意义。我不知道您使用的是 Python 2.x 还是 3.x，所以我将两种方式都解决。

在 2.x 中：range(n)必须计算n整数，并建立一个n长列表值。这似乎应该是O（n）。

在 3.x 中：range(n)只返回一个记住数字的对象n。那应该是 O(1)。但随后我们调用list它range，它必须迭代整个范围，计算所有n整数，并构建一个n长列表值。所以它仍然是O（n）。

把它放回你的循环，你有 O(log n) 次通过循环，每个 O(i) 复杂度。因此，总时间为 O(1) + O(2) + O(4) + O(…) + O(n/4) + O(n/2) + O(n)，其中 log(n)求和的步骤。换句话说，它是一个几何序列的总和。现在您可以解决问题了。（或者，如果不是，你被困在一个新的部分，如果你自己想不通，有人可以很简单地为你回答。）

你算出总和是-(1-2**log(n,2))。这不太对，因为你想要一个封闭的范围，而不是半开放的范围，所以它应该是-(1-2**log(n+1,2)). 但这可能是我没有解释清楚的错，并没有太大关系，所以我们先用你的版本。

2**log(n, 2)很明显n。（如果你对指数和对数的理解不够好，无法理解为什么，你应该找一个数学教程，但同时你可以用各种不同的值来测试它n来说服自己。）

同时，-(1-x)对于 anyx是公正的x-1。

所以，总和就是n-1。

如果您返回并使用正确的log(n+1, 2)而不是log(n, 2)，您将得到2n-1.

那么，这是正确的吗？让我们用一些实际数字进行测试。

如果n = 16，你得到1+2+4+8+16 = 31 = 2n-1。如果n = 1024，你得到1+2+4+…+256+512+1024 = 2047 = 2n-1。你扔给它的任何 2 的幂，你都会得到完全正确的答案。对于非 2 的幂，例如 1000，您会得到1+2+4+…+256+512+1000 = 2023，这不完全是2n-1，但它总是在 2 的因数内。（实际上，它是，n + 2**(ceil(log(n, 2)) - 1或者四舍五入到 2 的幂n + m - 1在哪里。）mn

无论如何，，，n-1……这些都是2n-1。n + 2**(ceil(log(n, 2)) - 1O(n)

你可以回过头来测试这个，用不同的值对整个函数计时，n然后看到，除了非常小的数字，当你加倍时，n它需要大约两倍的时间。

于 2013-11-11T21:49:14.927 回答
0

这个比看起来更棘手，因为它list(range(i))是基于 i 的，它以几何方式增长。然而，有一种简单的方法可以解决这个问题。相对于 n，总共创建了多少个元素？您可以通过假设方便的 n 值（即 2 的幂）来简化问题。

如果您仍然卡住，请从小处着手，然后再往上走。如果 n = 1，总共创建了多少个元素？然后看看你对 n = 2、n = 4、n = 8 等得到什么答案。该模式应该很快就会变得明显。

于 2013-11-11T21:56:31.447 回答