python时间复杂度和空间复杂度是指,时间复杂性与空间复杂性

复杂度和空间复杂度是指,时间复杂性与空间复杂性"/>

python时间复杂度和空间复杂度是指,时间复杂性与空间复杂性

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

array of length 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²)

^{pr2}$

示例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?

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

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

请注意，它可以更小，但是big-O符号表示的是一个上限。在

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

¹这假设我们已经将+、-、/、*、%等算术运算定义为基本运算，这通常都是这样做的。在