什么是算法时间复杂度?
算法的时间度量,记作:T(n) = O(f(n))。
它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,
称为算法的渐进时间复杂度,也就是时间复杂度。
推到大O 阶方法
1、用常数取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项中常数不是1,则去除。
通过上面三点处理之后得到的结果就是大O阶。
常见:
常数阶
时间复杂度(下面省略):O[1]
线性阶:O[n]
对数阶:O[logN]
平方阶:O[NM]
立方阶:O[NN*N]
指数阶:O[2(N)],备注:2的N次幂
耗费时间从小到大:
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2(n))<O(n!)<O(n*n)