计算xrange()， random.randint()和sort()函数的时间和空间复杂度

Question

Python中xrange()、random.randint(1,100)、sort()函数的时空复杂度是多少

import random
a = [random.randint(1,100)  for i in xrange(1000000)]
print a 
a.sort()
print a

Answer 1

如果没有关于问题的进一步信息，你的实际任务和你的解决尝试，一个答案可能仅仅是足够的…但我至少会给你一些建议。

a = [random.randint(1,100) for i in xrange(1000000)]

像a = ...这样的语句在时间复杂度方面通常被认为是0(1)。空间复杂度取决于您希望分析问题的详细程度。简而言之，一个列表中的1000.000个随机整数类似于0(1000.000)，因此是常数，因此可以说，依赖于输入长度(1000.000,2000.000，…)，它的结果是O(n)。

[random.randint(1,100) for i in xrange(1000000)]是一个for循环，有1,000.000个循环，并生成一个随机整数。在依赖于随机算法的情况下，它也会类似于O(n)。

a.sort()高度依赖于使用的排序算法。大多数语言使用归并排序，在任何情况下都是O(n * log(n))。

Answer 2

我在Facebook上得到了答案。感谢Shashank Gupta。

我假设你知道渐近符号的基本知识。

现在，暂时忘记a.sort()函数，专注于列表理解:A = [random.randint(1,100) for I in xrange(1000000)]

1000000太大了，所以现在我们把它减小到10。

a = [random.randint(1,100) for I in xrange(10)]

你正在构建一个包含10个元素的新列表。每个元素都是通过randint函数生成的。我们假设这个函数的时间复杂度是0 (1)对于10个元素，这个函数将被调用10次，对吧?

现在，我们来推广一下。对于整数nA = [random.randint(1,100) for I in xrange(n)]

您将调用randint函数'n'次。

所有这些也可以写成:对于I在xrange(n)中:a.append (randint (100)

这是O(n)。

代码后面是一个简单的print语句。这又是O(n)(在内部，python解释器遍历整个列表)。现在是排序部分。你已经使用了排序函数。要花多少时间?现在有很多排序算法，在不深入研究所使用的确切算法的情况下，我可以放心地假设时间复杂度为O(n log n)

因此，你的代码的实际时间复杂度是T(n) = O(n log n) + O(n)也就是O(n log n)(对于较大的n忽略下一项)

空间呢?您的代码初始化了一个大小为'n'的新列表。因此空间复杂度为O(n)。