我正在尝试查找以下代码片段的 Big O 运行时间:
for( i = 0; i < n * n; i++ )
for( j = 0; j < i; j++ )
k++;
我不确定由于 n 的乘法,它是否会是 O(n^3),或者只是 O(n^2)。一些帮助将不胜感激:)
内部循环将执行 0 + 1 + ... + n^2 - 2 + n^2 - 1 = (n^2)(n^2 - 1)/2 次(参见算术系列 http://mathworld.wolfram.com/ArithmeticSeries.html),所以实际上是 O(n^4)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)