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

Question

xrange()、random.randint(1,100) 和 sort() 函数在 Python

中的时间和 space 复杂度是多少

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 = ...这样的语句通常被认为在时间复杂度方面具有O(1)。 Space 复杂性取决于您希望分析问题的详细程度。简化的人可能会说列表中的 1.000.000 个随机整数类似于 O(1.000.000)，因此是常数，因此可以说依赖于输入长度 (1.000.000, 2.000.000, ...) 结果在 O(n).

[random.randint(1,100) for i in xrange(1000000)] 是一个包含 1.000.000 次循环并生成随机整数的 for 循环。根据 randint 算法，这也类似于 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 函数生成的。假设这个函数的时间复杂度是 O(1)。对于 10 个元素，这个函数将被调用 10 次，对吗？

现在，让我们概括一下。对于整数 'n' a = [random.randint(1,100) for i in xrange(n)]

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

所有这些也可以写成：对于 xrange(n) 中的 i： a.append(randint(1, 100))

这是 O(n)。

在代码之后，您有一个简单的打印语句。这又是 O(n)（在内部，python 解释器遍历整个列表）。现在是排序部分。您已经使用了排序功能。需要多少时间？那里有很多排序算法，并且在不考虑使用的确切算法的情况下，我可以安全地假设时间复杂度为 O(n log n)

因此，您的代码的实际时间复杂度为 T(n) = O(n log n) + O(n)，即 O(n log n)（对于较大的 n，忽略较低的项）

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

给你。

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

Calculating Time and Space Complexity of xrange(), random.randint() and sort() function

python

time-complexity

space-complexity