我试图通过一个简短的算法来理解时间和空间复杂度的差异。此代码接受一个列表/数组，并返回出现奇数次的单个数字。在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）的时间复杂度和空间复杂度，因为第一个循环仅仅在内存中创建了一个新的数据结构。
最佳答案
时间复杂度O（n^ 2）也是如此，因为我们在一次迭代上迭代了两次。
长度n的数组
时间复杂度是你的代码不是O(N²)。
在时间复杂度上对长度N的迭代被认为是O(N)。原因是，在大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)的上限，因为它必须检查列表中的每个元素。还是时间复杂度和空间复杂度每个＞O（n），因为第一个循环只是在内存中创建了一个新的数据结构？
在这种情况下，回路所做的本身与测量无关。相关的是在这里占主导地位的操作，这是使循环工作的比较和增量例如，
value % 2 != 0是一个恒定时间的操作，并且不会对代码的运行时间做出任何实质性的贡献。那么空间的复杂性是什么呢？
所需的空间也将取决于输入的大小和内容算法的最坏情况是一个由不同整数组成的数组，这意味着每个值都是唯一的。
如果每个值都是唯一的，那么每个值将导致添加一个键/值对。因此，该算法需要
O(1)空间。请注意，它可能更少，但是big-o表示法传达了一个上限。
请记住，通常情况下，在时间/空间约束之间也有一个折衷，更快的算法可能需要更多内存，而更节省内存的替代方案可能需要更多时间。
这假设我们已经定义了诸如
O(N)、+、-、/、*、%、等算术运算作为基本运算，这通常是完成的。