一、时间复杂度与空间复杂度
原文:时间复杂度与空间复杂度
二、主定理计算递推公式的时间复杂度
1、主定理的定义:
主定理的缺点:只能严格解决下面这种格式的递推公式(即递归算法的时间复杂度)
(1)例题:计算递推公式的时间复杂度
1)
2)
2、归并排序的时间复杂度与空间复杂度
排序算法之 归并排序 及其时间复杂度和空间复杂度
(1)时间复杂度的计算
(2)归并排序空间复杂度
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间:n + logn;所以空间复杂度为: O(n)
3、递归的方式计算 斐波那契 数列 时间复杂度与空间复杂度
(1)时间复杂度
(2)空间复杂度
解释: 计算 f6 时 需要调用 子函数,将f6 f5 f4 f3 均保留下来,因此改空间复杂的数量级与 n 同级 应该是 O(n)