嵌套循环的时间复杂度

Question

下面有一个程序可以计算最大成对积。

    for i in range(n):
     for j in range(i + 1, n):
       product = max(product, a[i] * a[j])

根据我的计算，上面的程序需要 (n^2 - n) 个步骤，其中 n 是元素的数量，但我正在阅读的书上写的是 n^2 个步骤。谁能帮我看看哪个是对的？

Answer 1

在处理大 O 表示法时，您总是采用最大幂项 - 逻辑很简单 - 随着 n 变大，n^2 将比 n 增长得更快，因此时间的增长率将占主导地位通过 n^2.

因此正确的大O是O(n^2)

Answer 2

在Big O Notation中，只考虑方程的最大次数项。例如，

1)n+7 - 这里我们只考虑 n 所以 O of n 是时间复杂度。

2)n^2 + n + 3 - 这里我们只考虑 n^2 所以 O of n^2 是时间复杂度。

3)3x(n^2) - 这里我们只考虑 n^2 所以 n^2 的 O 是时间复杂度。

由于大O符号是近似的时间复杂度，我们忽略所有小项。

对于你的等式 n^2 - n

将 n 视为 10000

n^2 = 100000000

n^2 - n = 99990000。这几乎等于 100000000 即 n^2

所以我们只考虑最高阶项。因此时间复杂度是 O(n^2)

嵌套循环的时间复杂度

Time complexity for the Nested Loops

python

algorithm

time-complexity

data-structures