对于上述斐波那契递归算法,其时间复杂度是O(2^N),随问题规模的增长,需要计算时间呈指数级增长,效率很低。
空间复杂度
空间复杂度反映了算法需要使用的辅助空间大小,与问题规模的关系。...它的时间复杂度是O(1),无论a为2000万,b为10亿,a+b还是O(1),因为a,b都是int 类型,都是32位,固定好的常数操作,&,/…都是O(1)
对数阶 O(logN)
// 计算BinarySearch...Σ(n-1)+(n-2)+...+1 = n(n-1)/2 = O(n^ 2) ,外层循环n次,内层循环每个都为O(n), 所以整体时间复杂度是外层循环次数乘内层循环时间复杂度,即O(n)×O(n)=O...{
// 这两个嵌套for循环的流程,时间复杂度为O(N * logN)
// 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/n,也叫"调和级数",收敛于.../2+N/3+N/4+....N/N-->N*(1+1/2+1/3+1/4+1/5+......1/N)->O(N*logN)
我们可以看出:对于循环嵌套,我们需要考虑所有细节,不能简单下定论,给出一个更准确的时间复杂度分析