时间复杂度 vs Space 复杂度
Time complexity vs Space complexity
我试图从一个简短的算法中理解时间和 space 复杂性之间的区别。此代码采用 list/array 和 returns 出现奇数次的单个数字。在 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 循环遍历数组的长度。但是第一个循环只是在内存中创建一个散列 table/dictionary 。时间复杂度也是 O(n^2)，因为我们两次迭代长度为 n 的数组，或者时间复杂度和 space 复杂度每个 O(n)，因为第一个循环只是创建一个新数据内存中的结构？
时间和space复杂度都是O(n)。
在大 O 表示法中，2n 和 n 没有区别，因此该算法具有 O(n) 行为。要具有 O(n^2) 行为，您的算法必须对数组中的每个元素 traverse/construct 整个数组一次。换句话说，您需要嵌套循环才能实现 O(n^2)。
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 时，常量对整体性能的影响开始变小。
这是不是说他们是"not important"；只是，随着 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?
所需的 space 还取决于输入的大小和内容。您的算法的最坏情况是 distinct 个整数数组，这意味着每个值都是唯一的。
如果每个值都是唯一的，则每个值都会导致添加 key/value 对。所以算法要求O(N)space.
请注意，它可能会更少，但大 O 符号表示 上限 界限。
请记住，通常 time/space 约束之间也存在权衡，其中更快的算法可能需要更多内存，而内存效率更高的替代方案可能需要更多时间。
¹这假设我们已经将 +、-、/、*、% 等算术运算定义为 基本操作，这是经常做的。
我试图从一个简短的算法中理解时间和 space 复杂性之间的区别。此代码采用 list/array 和 returns 出现奇数次的单个数字。在 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 循环遍历数组的长度。但是第一个循环只是在内存中创建一个散列 table/dictionary 。时间复杂度也是 O(n^2)，因为我们两次迭代长度为 n 的数组，或者时间复杂度和 space 复杂度每个 O(n)，因为第一个循环只是创建一个新数据内存中的结构？
时间和space复杂度都是O(n)。
在大 O 表示法中，2n 和 n 没有区别，因此该算法具有 O(n) 行为。要具有 O(n^2) 行为，您的算法必须对数组中的每个元素 traverse/construct 整个数组一次。换句话说，您需要嵌套循环才能实现 O(n^2)。
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 时，常量对整体性能的影响开始变小。
这是不是说他们是"not important"；只是，随着 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?
所需的 space 还取决于输入的大小和内容。您的算法的最坏情况是 distinct 个整数数组，这意味着每个值都是唯一的。
如果每个值都是唯一的，则每个值都会导致添加 key/value 对。所以算法要求O(N)space.
请注意，它可能会更少，但大 O 符号表示 上限 界限。
请记住，通常 time/space 约束之间也存在权衡，其中更快的算法可能需要更多内存，而内存效率更高的替代方案可能需要更多时间。
¹这假设我们已经将 +、-、/、*、% 等算术运算定义为 基本操作，这是经常做的。