【数据结构和算法】时间复杂度

算法必须讨论的问题：时间复杂度，简单介绍时间复杂度以及其计算方法

---

1 算法时间复杂度

1.1 介绍

• 时间复杂度：一个算法花费的时间与算法中语句的执行次数成正比，那个算法中语句执行次数多，它花费的时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为**T(n)**，n为方法调用次数

1.2 时间频度举例

• 计算：0~100的数字之和

@Test
public void test() {
	//方法一
	int count = 0;
	for (int i=0; i<=100; i++) {
		count += i;
	}
	System.out.println(count);
	//时间频度：T(n) = n + 1 --- 方法执行了n+1 （100+1，额外1次是最后判断>100跳出循环）


	//方法二：
	int start = 1;
	int end = 100;
	int total = (start + end) * end / 2;
	System.out.println(total);
	//时间频度为：T(n) = 1 --- 永远只执行1次
}

1.3 时间频度规则

• （1）在次数项复杂度比较时，可会忽略常数项
  • 例：2n+10 和 2n 差距不大，可以视为一样

• （2）在幂次项复杂度比较时，可以忽略低次数项
  • 例：n^3 + 3n 和 n^3 差距不大，可以视为一样

• （3）在幂次项复杂度比较时，可以忽略系数
  • 例：2n^3 和 n^3 差距不大，可以视为一样

1.4 时间复杂度

• （1）一般情况下，算法中的基础操作语句的重复执行次数为用 T(n) 表示，若有某个辅助函数f(n)**，当n取余无穷大时，T(n) / f(n) 无限趋于0，称f(n)是T(n)的同量级函数。记左T(n) = O(f(n))**，O(f(n))为渐进时间复杂度，简称时间复杂度

• （2）T(n)的不同，时间复杂度可能相同，也就是之前所讲的时间频度忽略规则。
• 例：T(n)=n^2+7n+6 和 T(n)=3n^3+2n+2 的时间复杂度都为O(n^2)

• （3）时间复杂度计算：f(n) = 时间频度的忽略规则，得出O(f(n))

1.5 常见时间复杂度

• 时间复杂度从小到大，上图按从上到大排序

• （1）常数阶
• 无论代码执行多少行，只要是没有循环等复杂结构，代码的时间复杂度都为O(1)

• （2）对数阶

  int i = 0;
  int n = 100;
  while(i < n) {
  	i = i * 2;
  }

• 在while循环里，每次都将i乘以2，乘完后，i举例n就越来越近，这种情况执行的次数就为log2(n)其他依次类推

• （3）线性阶

  int n = 100;
  for (int i=0; i<n; i++) {
  	System.out.println("hello");
  }

• 代码在for循环执行，for循环多大，n就多大，用O(n)来表示

• （4）线性对数阶

  int n = 100;
  for (int m=0; m<n; m++) {
  	int i = 0;
  	while(i < n) {
  		i = i * 2;
  	}
  }

• 在对数阶的情况下，套一个for循环包围，变成线性对数阶

• （5）平方阶 / 立方阶 / k次立方阶

  int n = 100;
  for(int i=0; i<n; i++) {
  	for(int j=0; j<n; j++) {
  		System.out.println("hello");
  	}
  }

• 平方阶就是多层for循环套用

1.6 其他时间复杂度

• （1）平均时间复杂度
• 指所有可能的驶入实例均以等概率出现的情况下，该算法的运行时间

• （2）最坏时间复杂度
• 时间复杂度最大的，称为最坏时间复杂度，一般讨论时间复杂度都围绕最坏时间复杂度讨论

• （3）空间复杂度
• 即算法运行时消耗的空间大小，一般不做讨论，很多时候都是用空间来换时间