算法考点

二分查找

概念：

二分查找是一种算法思想，当去查找范围内的一个数时，往往从中间开始，若中间数字比目标数字小，则从左边区间的中间位置为基点查找，反之，从右边区间查找，以此类推，查找到相应值。

时间复杂度：O(log₂(n))

大O表示法

算法的复杂段表现为T(n)=O(f(n))，其中O的含义是T(n)的数量级

渐近的时间复杂度

f

• O(1)

  int result = arr[2];
  

• O(log⁢₂n)

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

• O(n)

  for(int i = 0; i < n; i++);
  

• O(nlog⁢₂n)

  int count = 0;
  for(int i = 1 ; i <= n; i*=2){
      for(int j = 1; j <= n; j++){
          count++;
      }
  }
  

• O(n²)

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

• O(n³)

  int count = 0;
  for(int i = 1 ; i <= n; i++){
      for(int j = 1; j <= n; j++){
          for(int k = 1; k <= n;k++){
              count++;
          }
      }
  }
  

• O(2ⁿ)

  		int n = set.length;
          for (int i = 0; i < n; i++) {
              n >> 1; 
              for(int j = 0;j < n;j++);
          }
  

• O(n!)

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

• O(nⁿ)

          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= Math.pow(n, i); j++) {
                  System.out.println("i = " + i + ", j = " + j);
              }
          }