python-3.x 使用list.extend与显式使用2个循环的时间复杂度

uoifb46i 于 2023-03-20 发布在 Python

关注(0)|答案(1)|浏览(87)

基本上在我的问题中我有一个字典/数字Map比如hm 1

hm1={1:2, 2:1,4:1}

其中，Map的值即hm 1 [1]=2是频率。
我正试图根据Map中的这些频率创建一个列表。我为此写了2个代码。

for idx,num in enumerate(hm3):
        for i in range(hm3[num]):
            l.append(num)

l=[]所以它只是一个空列表。
以及代码2：

for n in hm3:
  l.extend( [n]*hm3[n])

看起来 * 代码2* 在运行后比代码1快，但是，list.extend([n])*hm3[n]操作的潜在时间复杂度是多少？
我知道外循环是'O（N）'，但我想知道.extend是如何工作的，因此，它是时间复杂度。
谢谢

1条答案

O（n^2）时间复杂度O（n^2）

for idx,num in enumerate(hm3):
        for i in range(hm3[num]):
            l.append(num)

时间复杂度O（n）
时间复杂度O（n）（假设内循环最多运行k次）
附加：O（1）
时间复杂度O（1）=O（n*k）

for n in hm3:
  l.extend( [n]*hm3[n])

时间复杂度O（n）
时间复杂度O（n）
时间复杂度O（n^2）
如果我想错了就告诉我。