一、时间复杂度和空间复杂度原文:时间复杂度和空间复杂度
二、主定理计算递归公式的时间复杂度1、主定理的定义:主定理的缺点:只能严格解决以下形式的递归公式,即递归算法的时间复杂度
(1)例题:计算递推公式的时间复杂度
1)
2 )
2、合并排序的时间复杂度和空间复杂度排序算法的合并排序及其时间复杂度和空间复杂度
(1)时间复杂度的计算
)合并排序空间复杂度合并的空间复杂度是其临时数组和递归时推入堆栈的数据所占用的空间: n logn; 因此,空间复杂度为3360o(n )
3、递归计算幸福服饰数列的时间复杂度和空间复杂度(1)时间复杂度
(2)空间复杂度的解释)由于在计算f6时需要调用子函数并保留所有f6 f5 f4 f3,因此改变空间复杂度的顺序应该与n相同级别为o(n )