博客

BigO

「时间空间复杂度」 = 时间和空间增长的趋势

「大O表示法」算法的渐进时间复杂度

     T(n) = O(f(n))

Eg:

// For Loop 
for(int i = 1; i <= n; i++ ){
		x++;
}

• 这段代码执行次数分析
  • int i = 1 会执行一次
  • i ≤n 执行 n次
  • x++ 执行 n次
  • i++执行n次
• 用BigO表示 O(1+3N) = O(N)
  • 当N无穷大的时候常量 1 就没有任何意义, 倍数3也没有意义了

Eg:

for(int i = 1; i<=n; i++){
	for(int j = 1;j<=n;j++){
		x++;
	}
}

• 同理 当N趋于无穷大的时候 外层 For Loop N次 x 内层For Loop N次
  • =⇒ O(N²)

Eg:

// For Loop 
for(int i = 1; i <= n; i++ ){
		x++;
}
for(int i = 1; i<=n; i++){
	for(int j = 1;j<=n;j++){
		x++;
	}
}

• ⇒ O(N+N²) ⇒ O(N²)
  • 当N趋于无穷大的时候 N 相对于 N² 而言就可以忽略不计了

常用的时间复杂度量级

• 常数阶O(1)

  
  
在这段代码的复杂度不会随着变量的变大而变长,也不会变得更复杂. 所以这样的代码重复不管多少遍,它的时间复杂度还是O(1)

  

  int x = 0;
  int y = 1;
  int temp = x;
  x = y;
  y = temp;
  

• 对数阶O(logN)

  
  
i 在Loop中会不断的变大,当i ≥ n的时候,就会跳出Loop. 那么i 什么时候会 ≥n? ⇒ 2ᴷ = N ⇒ K = logN

  

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

• 线性阶O(N)

  
  
这段代码的时间复杂度取决于N的大小,N越大,时间复杂度就越大

  

  // For Loop 
  for(int i = 1; i <= n; i++ ){
  		x++;
  }
  

• 线性对数阶O(nlogN)

  
  
很好理解,就是在logN的外面加一层 N 层的循环

  ⇒ N层循环次数 * logN
  

  // For Loop 
  for(int i = 1; i <= n; i++ ){
  	  int x = 1;
  		while(x < n){
  			x = x * 2;
  	}
  }
  

• 平方阶O(N²)

  for(int i = 1; i<=n; i++){
  	for(int j = 1;j<=n;j++){
  		x++;
  	}
  }
  

• 立方阶O(N³)

• K次方阶O(Nᴷ)

• 指数阶(2ᴺ)

• 阶乘O(N!)

其他复杂度指标

• O(Big O) 最差情况

• Ω(Big Omega) 最好的情况

• Θ(Big Theta) 一个算法的区间

空间复杂度

「空间复杂度」 : 内存空间增长的趋势

常用的空间复杂度

• O(1)

  
*这段代码需要的空间是一个常数量,x和y的值不会影响内存的空间分配*


  int x = 0;
  int y = 0;
  x++;
  y++;
  

• O(N)

  
  
代码中创建了一个数组,数组的长度是n.

  

  
  
当n=3的时候,就会给这个数组进行赋值(0,1,2);当n=5的时候,给数组进行赋值(0,1,2,3,4).所以这个数组的n越大的话,算法 的复杂度就越高,需要分配的空间也就越多

  

  int[] newArray = new int[n];
  for(int i = 0;i < n;i++){
  		newArray[i] = i;
  }
  

• O(N²)

  int[][] newArray = new int[n][n];
  for(int i = 0;i < n;i++){
  	for(int j = 0;j < n;j++){
  		newArray[i][j] = i; 
  	}
  }
  

  
  
  主流排序算法(摘自小灰算法之旅)
  

1. 时间复杂度为O(N²)的排序算法
   1. 冒泡排序
   2. 选择排序
   3. 插入排序
   4. 希尔排序(希尔排序比较特殊,它的性能略优于O(N²),但又比不上O(nlogN),姑且把它归入本类)
2. 时间复杂度为O(nlogN)的排序算法
   1. 快速排序
   2. 归并排序
   3. 堆排序
3. 时间复杂度为线性的排序算法
   1. 计数排序
   2. 桶排序
   3. 基数排序