python - 时间复杂度与空间复杂度

Question

我试图通过一个简短的算法来理解时间复杂度和空间复杂度之间的区别。此代码采用列表/数组并返回出现奇数次的单个数字。在 Python 中:

def foo(array_of_ints):
    hash_table = dict()
    for i in array_of_ints:
        hash_table[i] = hash_table.setdefault(i, 0) + 1
    for key, value in hash_table.items():
        if value%2 != 0:
            return key

有两个 for 循环遍历数组的长度。但是第一个循环只是在内存中创建一个哈希表/字典。时间复杂度也是 O(n^2)，因为我们两次迭代长度为 n 的数组，或者时间复杂度和空间复杂度都是 O(n)，因为第一个循环只是在内存中创建一个新的数据结构？

Answer 1

So is the time complexity O(n^2), because we twice iterate over an array of length n

您的代码的时间复杂度不是O(N²)。

迭代长度为 N 的集合在时间复杂度上被认为是 O(N)。原因是，在 Big-Oh 表示法中，您总是对控制 函数的项感兴趣。当您达到足够大的 N 时，常量对整体性能的影响开始变小。

这不是说它们“不重要”；只是，随着 N 趋于无穷大，这些常量的实际效果更类似于向海洋中再添加一滴或一桶水。这种表示法旨在让您粗略(不准确)地了解算法的预期行为 - 即随着输入大小的增长，它缩放的效果如何。

这意味着您的函数可以在同一个集合上迭代 5 次，这将是 O(5N)，它仍然是 O(N)。

但是你如何得到O(N²)呢？您会开始将这些视为开始嵌套循环。

示例A - O(N)

def linear(integers):
    # no nesting
    for i in integers: print(i)
    for i in integers: print(i+1)

示例 B - O(N²)

def quadratic(integers):
    # notice double nesting
    for i in integers:
        for j in integers:
            print(i+j)

示例 C - O(N³)

def cubed(integers):
    # notice triple-nesting
    for i in integers:
        for j in integers:
            for k in integers:
                print(i+j+k)

如果您使用矩阵，您将找到 O(N³) 算法的示例，至少如果您使用的是朴素的实现。如果你不清楚，这叫做 asymptotic notation .

另请注意 Big-Oh notation表示算法运行时间的上限。这意味着它是对最坏情况的衡量。

例如，线性搜索列表中不存在的项目将使您的算法达到 O(N) 的上限，因为它必须检查列表中的每个元素。

or is the time complexity and space complexity each > O(n), since the first loop simply creates a new data structure in memory?

在这种情况下，循环正在做什么本身与测量无关。相关的是这里占主导地位的操作，它们是使循环工作的比较和增量。例如，value % 2 != 0 是一个常量时间操作¹，或 O(1)，不会对代码的运行时间做出任何实质性贡献.

So what is the space-complexity?

所需的空间还取决于输入的大小和内容。您的算法的最坏情况是不同 整数数组，这意味着每个值都是唯一的。

如果每个值都是唯一的，那么每个值都会导致添加一个键/值对。因此，该算法需要O(N)空间。

请注意，它可能会更少，但大 O 符号传达了一个上限边界。

请记住，通常情况下，时间/空间限制之间也存在权衡，其中更快的算法可能需要更多内存，而内存效率更高的替代方案可能需要更多时间。

---

¹这假设我们已经定义了算术运算，例如 +、-、/、*、% 等作为基本操作，这是很常见的。