-
时间复杂度:随着n的不断變化T(n)/f(n)逐渐趋近于一个常数,我们使用O(f(n))来表示时间复杂度
时间复杂度就是: 程序循环体内执行次数最多的语句的执行次数,若并列的循環则将并列循环的时间复杂度相加。
-
1.首先找到执行次数最多的基本语句一般都是在最内层循环的循环体内
2.查看该基本语句执行的次数
3.對于并列循环,则把复杂度相加得出最后该程序的时间复杂度
(保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次冪和最高次幂的系数) -
核心:n是不变的就执行固定次数,有限的;
Ο(1)表示基本语句的执行次数是一个常数一般来说,只要算法中不存在循環语句其时间复杂度就是Ο(1)
i一次增长2倍,也就是说超过n需要执行多少次语句,即为时间复杂度通过计算2^i=n,得到i=logn.所以时间复杂度为对數阶O(logn).
n是因为一次增长一步n次后执行完了这条语句,所以为O(n)
这段代码执行了2n^2+2n+3次,即O(n2)随着这段代码重复被执行的次数增多,随著n值增大时间效率会爆炸式增长。时间复杂度:O(n2)
- O(1)常数阶:每条语句的频度都是1算法的执行时间不随着问题规模n增大而增长,即使有上千条语句其执行时间也不过是一个比较大的常数。
- O(n)线性阶:有一个n次循环的循环语句随着n增长执行时间线性增长。
- O(n^2)平方阶:循环中嵌套一个循環的情况