嵌套循环的时间复杂度

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表示法中，只考虑方程的最大阶项。 例如

< p＞1＞强＞n+7＜强＞-这里我们将考虑n仅为<<强> O的n<强>是时间复杂度。

< p＞2）<强> n ^ 2＋n＋3 < /强> -这里我们将考虑n^ 2，只有n> 2 < <强> >强> >时间复杂度。

< p＞3）<强> 3x（n^ 2）< /强> -这里我们将考虑n^ 2，只有n> 2＜/强>的强＞O是时间复杂度。

由于大O表示法是近似的时间复杂度，我们忽略了所有的小项

对于你的方程式n^2-n

考虑<强> n AS＞10000＞/强>

n^2=100000000

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

<>我们只考虑最高度项。因此，时间复杂度是O（n^2）

Answer 2

当处理大O符号时，你总是使用最大的幂项-逻辑很简单-因为n变大，n^2将比n增长得更快，因此时间的增长率将由n^2控制

因此，正确的大O是O（n^2）