我有一个程序可以计算最大成对乘积。
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 步骤。
谁能帮助我理解哪个是正确的?
在大 O 表示法中,仅考虑方程的最大次数项。
例如,
1)n+7- 这里我们只考虑nO of n是时间复杂度。
2)n^2 + n + 3- 这里我们只考虑n^2O of n^2是时间复杂度。
3)3x(n^2)- 这里我们只考虑n^2O of n^2是时间复杂度。
由于大 O 表示法是近似时间复杂度,因此我们忽略所有小项。
对于你的方程n^2 - n
考虑n as 10000
n^2 = 100000000
n^2 - n = 99990000。这几乎等于100000000 即 n^2
所以我们只考虑最高阶项。因此时间复杂度为O(n^2)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)