算法-时间复杂度
2020-04-06 本文已影响0人
AGEGG
大O
n表示数据规模
O(f(n))表示运行算法所需执行的指令数，和f(n)成正比
image.png
image.png
image.png
image.png
image.png
对数据规模有一个概念
image.png
image.png
image.png
常见的复杂度分析
image.png
单循环
image.png
即使一半但线性增加
image.png
双重循环
image.png
不能见双重循环为O(n^2)
image.png
二分查找法
image.png
image.png
image.png
image.png
这个是O(nlogn)
第一层为sz经过几次除2要大于等于n，为longn
第二层n
image.png
O 根号n
image.png
复杂度实验
实验，观察趋势
每次讲数据规模提高两倍，看时间的变化
递归算法的时间复杂度分析
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
拓展资料：主定理
均摊复杂度分析
多个算法平均
比如O(1)算法 第n次为O(n),平均为2，因此还是 O(1)
