算法导论（一）——渐近分析，递归解法

前言:

算法分析即关于计算机程序性能和资源利用的理论分析。

好的程序需要具有：正确性，安全性，用户友好性，可维护性，简洁性……

程序性能指一个程序对内存和时间的要求，可以通过性能分析或者性能试验来确定。分析一般有时间复杂度和空间复杂度两个方面。空间复杂度包括：指令空间，数据空间，环境栈空间，一般计算空间需求的可变部分（动态分配空间+递归栈空间）。时间复杂度取决于输入分布，输入规模，评估的最大时间，一般计算平均操作步数。

 

1.  渐近分析

即不关注实际实际时间，而关注如何增长。不考虑机器的计算能力，而关注随着数据输入规模变大时间的增长。舍去低阶项和常数项

渐进复杂度的分析是有局限性的。对一些小的实例，复杂度为的插入排序比所有复杂度为的排序法具有更好的性能。

2.  递归解法

替换法，递归树法，主方法（f(n)与logba比较，取大者，相等时多乘以个lgn）