算法分析
算法时间复杂度
算法时间复杂度来度量算法的执行时间长短。
比较算法随着输入规模的增长量时，可以有以下规则：
1.算法函数中的常数可以忽略；
2.算法函数中最高次幂的常数因子可以忽略；
3.算法函数中最高次幂越小，算法效率越高。
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。
image.png
复杂程度从低到高依次为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
根据折线图分析，我们会发现，从平方阶开始，随着输入规模的增大，时间成本会急剧增大，所以尽可能的追求的是O(1),O(logn),O(n),O(nlogn)这几种时间复杂度，
最好情况：
查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
最坏情况：
查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
平均情况：
任何数字查找的平均成本是O(n/2)
算法空间复杂度
算法的空间复杂度来描述算法对内存的占用
申请开辟的额外内存
网友评论