代码时间复杂度计算

时间复杂度公示:
代码时间复杂度计算
下面分析一段代码:
代码时间复杂度计算
2、3、4行每一行都需要1个单位的执行时间,5、6行循环了N边,需要2N个单位时间,7、8行执行了n^2遍,所以一共需要执行时间:(2N ^2 + 2N + 3 )*单位时间。
我们用T(n) 表示,O表示T(n)与f(n)成正比(单位时间),所以表达式可以写成:T(n) = O(2N ^2 + 2N + 3 ) ,这就是大O时间复杂度表示法,由于N无穷大,所以只需要表示最大量级即可,即:T(n) = O(N ^2 )

时间复杂度分析:

1、只关注循环执行次数最多的一段代码;
2、加法法则:总复杂度等于量级最大的那段代码的复杂度;
例如:时间复杂度:T(n) = O(N+N ^2 ) = O(N ^2 )
代码时间复杂度计算

3、乘法法则:嵌套代码的复杂度等于嵌套内外代码的复杂度乘积;
例如:
以下算法时间复杂度为:T(n) = O(N X N)=O(N ^2 )
代码时间复杂度计算