我如何检查理解的时间复杂度

Question

我浏览了很多关于 python 时间复杂度的博客并提出了我的疑问：

在列表理解的情况下，如何分析时间复杂度？

例如：

x = [(i,xyz_list.count(i)) for i in xyz_set]

其中 xyz_list = [1,1,1,1,3,3,4,5,3,2,2,4,5,3] 和 xyz_set = set([1, 2, 3, 4, 5])

那么，复杂的是一行代码 O(n*n*n) [即 O(n) 用于迭代，O(n) 用于列表创建，O(n) 用于计数函数]？？

Answer 1

这是二次方O(n^2):

x = [(i,xyz_list.count(i)) for i in xyz_set]

xyz_list.count(i)) #  0(n) operation

对于 xyz_set 中的每个 i 你做一个 0(n) xyz_list.count(i)

您可以使用双 for 循环来编写它，这样会更明显：

res = []
for i in xyz_set: # 0(n)
    count = 0
    for j in xyz_list: # 0(n)
        if i == j: # constant operation 0(1) 
            count += 1 # constant operation 0(1)
    res.append(count) # constant operation 0(1)

Python time complexity

通常当你看到双 for 循环时，复杂度将是二次的，除非你正在处理一些常数，例如我们只想检查 xyz_list 的前 7 个元素，然后是运行时间将是 0(n) 假设我们在内部进行相同的持续工作 for:

sec = 7
res = []
for i in xyz_set: 
    count = 0
    for j in xyz_list[:sec]: 
        ......

Answer 2

复杂性不一定成倍增加。在许多情况下，它们只是相加。

你的情况： O(n) 用于迭代，O(n) 用于列表创建，对于每个新项目，count() 有 O(n)，这给出 n*O(n)。总复杂度为 O(n) + O(n) + n*O(n) = O(n*n)

Answer 3

列表理解没什么特别的，它只是一个循环。您可以将代码重写为：

x = []
for i in xyz_set:
    item = (i, xyz_list.count(i))
    x.append(item)

所以我们有一个循环，我们有一个 O(n) list.count() 操作，使得算法 O(N**2)（二次）。

我如何检查理解的时间复杂度

How do i check the time complexity of a comprehension

python

list-comprehension

python-2.7