我有以下算法,运行时复杂度为 O(N^2) 但我想对其有更深入的了解,而不是仅仅记住常见的运行时。
分解和分析它的正确方法是什么i+1
考虑在内层 for 循环中吗?
void printunorderedPairs(int[] array) {
for(int i=0; i<array.length; i++) {
for(int j=i+1; j<array.length; j++) {
System.out.println(array[i] + "," + array[j]);
}
}
}
EDIT
询问如何分析特定问题
分解和分析它的正确方法是什么
拿起铅笔和纸,放下一些展开的环:
i inner loops per i
-------------------------------
1 length - 1
2 length - 2
.. ..
k length - k
.. ..
length - 1 1
length 0
现在,为了获得所需的总时间,我们对内部循环进行总结:
(length - 1) + (length - 2) + ... + (length - k) ... + 1 + 0
这是一个算术级数,它的和是
((length - 1) + 0) / 2 * length == length**2 / 2 - length / 2 = O(length**2)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)