python find方法的复杂度_寻找特定python算法的时间复杂度

待我称王封你为后i 2023-10-05 18:11 5阅读 0赞

您已经知道它运行int(log(n, 2))次迭代。(您可以很容易地测试这一点，只需在循环中添加一个计数器，然后用1、2、4、8、16、32、64等调用它，并看到计数器每次n加倍时增加1。)

现在你想知道循环内部需要多长时间。这里，您需要知道range和\{\}函数的时间复杂性。我可以给你答案，事实上你可以猜出来，但你不能真正证明这一点，除非你开始读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)，对吗？在

让我们验证一下这是否合理。我不知道您使用的是python2.x还是3.x，所以我会用两种方法来解决。在

在2.x中：range(n)必须计算n个整数，并构建一个长n值的列表。看起来应该是O(n)。在

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

把它放回你的循环，你有O(logn)次循环，每一次O(i)复杂度。因此，总时间为O(1)+O(2)+O(4)+O(…)+O(n/4)+O(n/2)+O(n)，总和的步数为对数(n)。换句话说，它是geometric sequence的和。现在你可以解决问题了。(或者，如果不是的话，你就被困在一个新的部分，如果你自己想不出来的话，有人可以很简单地为你作答。)

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

2\*\*log(n, 2)显然是\{\}。(如果你对求幂和对数的理解还不足以理解为什么，你应该找一本数学教程，但同时你可以用各种不同的n来测试它，以说服自己。)

同时，任何x的-(1-x)就是x-1。在

所以，总和就是n-1。在

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

那么，对吗？让我们用一些实际数字来测试。在

如果n = 16，则得到\{\}。如果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，或者n + m - 1，其中m是\{\}四舍五入到2的幂次方。)

不管怎样，n-1，2n-1，n + 2\*\*(ceil(log(n, 2)) - 1……这些都是\{\}。在

你可以回过头来测试这一点，用不同的值n来计时整个函数，看看除了非常小的数字之外，当你加倍n时，所花的时间大约是原来的两倍。在