【算法】程序的时间复杂度计算

时间复杂度的概念。

定义：存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表⽰为 T(n) = O(f(n)) 。

很多时候⼀眼就能看出程序的时间复杂度，但是遇到复杂的就需要将其过程推导出来，为此总结以下两种形式⼀、循环主体中的变量参与循环条件的判断

找出主体语句中与T(n)成 正⽐的循环变量，带⼊进⾏计算，例如：int i = 1;while(i <= n) i = i*2;

其中i*2的次数与T(n)成正⽐，则2的T(n)次⽅<= n,则T(n)<=log2n。

计算时间复杂度--（简单版）

步骤：

1、找到执⾏次数最多的语句2、语句执⾏语句的数量级3、⽤O表⽰结果

计算时间复杂度的3个出发点，掌握这三个出发点，那么⼀向搞不懂的时间复杂度就可以迎刃⽽解啦。然后：

1、⽤常数1取代运⾏时间中的所有加法常数2、在修改后的运⾏次数函数中，只保留最⾼阶项

3、如果最⾼阶项存在且不是1，那么我们就去除于这个项相乘的常数。⽐如3n^2我们取n^2最后就可以得到你们想要的结果了。举⼏个例⼦：

我们来看⼀下这个例⼦，⽤的是java，内容就是打印8条语句，问这个程序的时间复杂度是多少？public class TS {

public static void main(String[] args) { System.out.println(\"111\"); System.out.println(\"111\"); System.out.println(\"111\"); System.out.println(\"111\"); System.out.println(\"111\"); System.out.println(\"111\"); System.out.println(\"111\"); System.out.println(\"111\"); }}

O（8）？ 当然不是按照时间复杂度的概念“T（n）是关于问题规模为n的函数”，这⾥跟问题规模有关系吗？没有关系，⽤我们的第⼀个⽅法，时间复杂度为O（1）。

第⼆个例⼦：（线性阶）

public class TS {

public static void main(String[] args) { int sum = 0;

for(int i=1;i<=100;i++) { sum = sum + i;

} }}

时间复杂度为O（n）。

第三个例⼦：（平⽅阶）

public class TS {

public static void main(String[] args) { int sum = 0;

for(int i=1;i<=100;i++) { for(int j=1;j<=100;j++) sum = sum + i; } }}

外层i的循环执⾏⼀次，内层j的循环就要执⾏100次，所以外层执⾏100次，那么总的就需要执⾏100*100次，那么n次呢？就是n的平⽅次了。所以时间复杂度为：O（n^2）。平⽅阶的另外⼀个例⼦：

public class TS {

public static void main(String[] args) { int sum = 0;

for(int i=1;i<=100;i++) { for(int j=i;j<=100;j++) sum = sum + i; } }}

当i=1的时候执⾏n次，当n=2的时候执⾏（n-1）次，......

⼀直这样⼦下去就可以构造出⼀个等差数列：n+（n-1）+（n-2）+......+2+1根据等差数列的求和公式：或者

求和易得：n+n*(n-1)/2整理⼀下就是n*(n+1)/2然后我们将其展开可以得到n^2/2+n/2。根据我们的步骤⾛，保留最⾼次项，去掉相乘的常数就可以得到时间复杂度为：O（n^2）第四个例⼦：（对数阶）

public class TS {

public static void main(String[] args) { int i=1; int n= 100; while(i2^x = n,所以时间复杂度为O(log2n)。

补充常⽤的时间复杂度所耗费的时间从⼩到⼤依次是：

O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)