数据结构和算法分析（二）

算法分析

算法时间复杂度

算法时间复杂度来度量算法的执行时间长短。

比较算法随着输入规模的增长量时，可以有以下规则：
1.算法函数中的常数可以忽略；
2.算法函数中最高次幂的常数因子可以忽略；
3.算法函数中最高次幂越小，算法效率越高。

用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。

image.png
复杂程度从低到高依次为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)
根据折线图分析，我们会发现，从平方阶开始，随着输入规模的增大，时间成本会急剧增大，所以尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度，

最好情况：
查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
最坏情况：
查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
平均情况：
任何数字查找的平均成本是O(n/2)

算法空间复杂度

算法的空间复杂度来描述算法对内存的占用
申请开辟的额外内存