算法基础课 2.4 复杂度

注意 图片中lg 不准确 应为log 2

冒泡排序 选择排序 插入排序 复杂度 O(n^2)

Arrays.sort() 复杂度 nlogn （lg 是10为底数 ln 是e为底数 log 不常用 是2为底数）

常用的 2^27 = 10 ^ 8

10 ^8 是1亿 （万个万）

顺序查找 复杂度 n
二分查找 复杂度 logn （图上错了 应是以2为底数）

降低复杂度一个层次 效率提高很多

最大公约数 辗转相除法 复杂度O(log2N)

从这里可以发现 每调两次函数 n就会消减一半O (每两次折半 2log2N) (定理 m%n < m/2)

2    n/2
4    n/4
6    n/8
。  。 。
。  。 。
x    n/2^(x/2)

斐波那契 （汉诺塔同理）复杂度O(2^n)