4.3 时间复杂度.md

时间复杂度

https://pic2.zhimg.com/80/v2-8c710914a7d092296dd4c2eadb525dcd_hd.jpg

• https://www.jianshu.com/p/f4cca5ce055a

1、How to Check if an Array Contains a Value in Java Efficiently?

public static boolean useArraysBinarySearch(String[] arr, String targetValue) {	
	int a =  Arrays.binarySearch(arr, targetValue);
	if(a > 0)
		return true;
	else
		return false;
}

2、A little Quiz: Why substring() method in JDK 6 can cause memory leaks?

• 同下

3、The substring() Method in JDK 6 and JDK 7

• 存在性能问题
• 1.7做了优化

时间复杂度和空间复杂度

• 常数阶O(1)

  k次方阶O(n^k),指数阶O(2^n)

• 线性阶O(n)

  for(int i = 0; i < n; i++){
      printf("%d ",i);
  }  

• 平方阶O(n^2)

  for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
          printf("%d ",i);
      }
  }   
  //运行次数为(1+n)*n/2
  //时间复杂度O(n^2)

• 对数阶O(log2n)

  int i = 1, n = 100;
  while(i < n){
      i = i * 2;
  }
  //设执行次数为x. 2^x = n 即x = log2n
  //时间复杂度O(log2n)

• 线性对数阶O(nlog2n)

• 立方阶O(n^3)

• k次方阶O(n^k)

• 指数阶O(2^n)

• 常用排序算法的时间复杂度

        最差时间分析  平均时间复杂度 稳定度     空间复杂度   
  冒泡排序    O(n2)   O(n2)       稳定        O(1)  
  快速排序    O(n2)   O(n*log2n)  不稳定  O(log2n)~O(n)     
  选择排序    O(n2)   O(n2)       稳定      O(1)    
  二叉树排序  O(n2) O(n*log2n)    不稳定     O(n)     
  插入排序    O(n2)   O(n2)       稳定      O(1)    
  堆排序  O(n*log2n) O(n*log2n)   不稳定     O(1)    
  希尔排序    O        O          不稳定     O(1)
  

• ArrayList vs LinkedList

                     | Arraylist | LinkedList
   ------------------------------------------
   get(index)        |    O(1)   |   O(n)
   add(E)            |    O(n)   |   O(1)
   add(E, index)     |    O(n)   |   O(n)
   remove(index)     |    O(n)   |   O(n)
   Iterator.remove() |    O(n)   |   O(1)
   Iterator.add(E)   |    O(n)   |   O(1)