这个遍历列表 a 创建字典的函数的时间复杂度是多少？

Question

我有一个功能可以以某种方式重新排列输入列表和 returns 输出列表。我对函数的时间和 space 复杂性感到困惑。下面是代码：

def rearrange_list(inp_list):
    d = {}
    output_list = []
    for num in inp_list:
        if num in d:
            d[num] += 1
        else:
            d[num] = 0
            output_list.append(num)
    for k,v in d.items():
        if v > 0:
            for i in range(v):
                output_list.append(k)
    return output_list

这是我的复杂性分析：

时间复杂度： O(n + m²) 其中 n 是输入列表的长度，m 是字典的大小
Space 复杂度： O(n) 其中 n 是输入列表的长度

我的主要困惑是我是否也应该考虑遍历 O(n) 字典，因为最坏的情况是我们将在列表中有 n 个项目，或者它应该像我在分析中所做的那样用 m 表示它，因为它可以是从 0 到 n 的任何值？

提前感谢您的帮助！

Answer 1

你的时间和 space 复杂度都是 Theta(n)。虽然有时在不改变渐近值的时间或 space 复杂度中包含术语可能有助于清晰度（一个典型的例子是 string searching algorithms），但它在这里没有多大意义.

虽然你声称 O(n + m^2) 时间复杂度在技术上是正确的，因为 Big-O 符号是上限，但你可以证明 O(n) 也是上限，因为字典有大小最多 n 并且我们只对每个键进行一次迭代：从输入中读取了 n 项，字典最多 n 次循环迭代，并且附加了 n 项到输出列表。

如果需要，您可以计算所需的 'auxiliary' space，这将是所需的 space 的数量，但不包括输入或输出数组。在这里，那将是 Theta(m)。但是，您应该注意，此类分析并不常见：根据假设，除非另有说明，space 复杂性分析将包括输出的大小。

为了解决关于为什么第二个循环仍然是具有许多重复值的线性时间的常见混淆，让我们看一个例子。

有问题的行是：

for k, v in d.items():
    if v > 0:
        for i in range(v):
            output_list.append(k)

假设我们的输入列表是 [1, 1, 1, 1, 1, 1, 1, 2, 2, 2]（总共十个元素：七个“1”和三个“2”）。

然后我们的dictionary.items()（每个元素的计数减一）看起来像：[(key: 1, value: 6), (key: 2, value: 2)]（它在内部并没有真正存储为Python元组列表，但这些是项目的全部内容 view-object).

让我们逐行分析第二个循环的操作：

for k, v in [(key: 1, value: 6), (key: 2, value: 2)]: 
# On our first iteration, so k = 1, v = 6.

    if 6 > 0:                      # 1 operation
        for i in range(6):         # 6 operations
            output_list.append(1)  # 6 operations

# For the (k, v) pair of (1, 6), the inner-loop has run 6 times.
# Every time the inner-loop runs, the length of output_list
# increases by 1

# Second iteration of outer-loop runs again:
for k, v in [(key: 1, value: 6), (key: 2, value: 2)]: 
# On our second iteration, so k = 2, v = 2.

    if 2 > 0:                      # 1 operation
        for i in range(2):         # 2 operations
            output_list.append(2)  # 2 operations

# For the (k, v) pair of (1, 6), the inner loop has run 2 times.
# In total: 8 inner-loop iterations, and output_list has len 8

在非正式的复杂性分析中，'standard' 经验法则是 double-nested 循环的 run-time 通常是二次的。这是因为我们正在计算 inner-loop 迭代的总数，例如

for i in range(n):
    for j in range(n):

作为

(n inner-loops per outer-loop) * (n outer-loops) = n^2 inner-loops

当 inner-loop 迭代次数根据 outer-loop 的状态发生显着变化时，不应应用此假设。在我们的示例中，inner-loop 次迭代是 v，这取决于外部循环。

要在此处找到运行时间，我们需要一种不同的方法来计算发生了多少次 inner-loop 迭代。幸运的是，我们可以做到这一点：在每个 inner-loop 迭代中，我们将一个元素附加到 output_list.

由于 output_list 的最终长度是 n，我们知道 inner-loop 最多执行了 n 次（从技术上讲，它恰好执行了 n-m 次，因为在较早的 dictionary-initializing 循环终止后 output_list 已经有大小 m）。与其错误地将其乘以 m，outer-loop 迭代次数，我们应该为 Theta(n+m) 的运行时间添加内循环和外循环迭代，即 Theta(n)。

附录：评论正确地指出，因为 Python 字典没有 O(1) 摊销 worst-case lookup/insert 时间保证，所以第一个循环最多就是Omega(m*n)。而 Python 使用 pseudo-random probing on an open-addressing table, this only ensures good 'average' performance. Thanks to Kelly Bundy 进行信息丰富的讨论和更正。

不幸的是，虽然 O(1) 分摊 worst-case lookup/insert 散列是可能的，例如 Cuckoo hashing，但实际上这比当前使用的散列平均慢得多大多数标准库，并且在不久的将来不太可能改变。

Answer 2

时间复杂度

您可以将代码分为两部分。

第 1 部分

for num in inp_list:
    if num in d:
        d[num] += 1
    else:
        d[num] = 0
        output_list.append(num)

在第一行中循环访问 inp_list，并且在每次循环中调用 if num in d。 python 所做的是搜索字典 d 的键，因此这部分的时间复杂度为 O(nm)，其中 n 是 inp_list 的大小，m 是数字的大小inp_list.

中的唯一值

第 2 部分

for k,v in d.items():
    if v > 0:
        for i in range(v):
            output_list.append(k)

在这部分中，您将遍历第一行中字典的大小，即 O(m)。我忽略了嵌套的 for 循环，因为循环可以替换为以下内容：

output_list = output_list + [k] * v

这发生在 O(1)

综上所述，时间复杂度应该是O(nm + m) = O (m(n+1)) = O(nm)。

然而，由于d是一个字典，关键搜索需要O(1)而不是O(m)(查看更多here)，使得时间复杂度下降到O(n)。

Space 复杂度

由于创建了具有 m 个键的字典（其中 m 是 inp_list 中唯一值的数量，space 复杂度为 O(n+m) < O(2n) = O (n)

Answer 3

逐步分解算法：

第一个 for 循环 (for num in inp_list)。
它只是简单地遍历列表，这需要 O(N) 时间，并且字典的大小为 O(number of unique elements in list)，可以概括为 O(N) space（其中 N =列表长度 = 唯一键的最大可能数量）。
第二个 for 循环（for k,v in d.items()）。
这将遍历 dict 中的键，这些键的计数为 O(number of unique elements in list)。
第三个 for 循环（for i in range(v)）。
由于 v 的总和只是列表中重复元素的计数，因此它的上限为 O(N).

更好的近似算法应该是O(N)时间和space，而不是建议的O(n + m^2)

这个遍历列表 a 创建字典的函数的时间复杂度是多少？

What is the time complexity of this function that iterates through a list a creates a dictionary?

python

algorithm

analysis

time-complexity

space-complexity

时间复杂度

Space 复杂度