一、大O表示法（Big O）

• 一般用大 O 表示法來描述復雜度，它表示的是數據規(guī)模 n 對應的復雜度。
• 忽略常數、系數、低階
  9 >> O(1)
  2n + 3 >>O(n)
  n^2 + 2n^2 + 6 >> o(n^2)
  4n^3 + 3n^2 + 22n + 100 >> O(n^3)
• 注意： 大 O 表示法僅僅是一種粗略的分析模型，是一種估算，能幫助我們短時間內了解一個算法的執(zhí)行效率。

執(zhí)行次數	復雜度	非正式術語
12		常數階
4log2(n) + 25		對數階
2n + 3		線性階
3n + 2nlog3(n) + 15		nlogn階
4n^2 + 2n + 6		平方階
4n^3 + 3n^2 + 22n + 100		立方階
2^n		指數階

• O(1) < O(longn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
• 可以借助函數生成工具對比復雜度的大小
  https://zh.numberempire.com/graphingcalculator.php

對數階的細節(jié)

• 對數階一般省略底數
  因為不管底數是什么，都可以通過轉換為一個常數*log2(n)
  log2(n) = log2(9) * log9(n)
  又因為2為底的可以省略2。
• 所以 log2(n)、log9(n)統(tǒng)稱為log(n)

• 時間復雜度（time complexity）：估算程序指令的執(zhí)行次數。這里的大O的意思是估算程序最終的執(zhí)行次數是多少。
• 空間復雜度（space complexity）：估算所需占用的存儲空間。

二、示例

public static void test1(int n) {
  // 1
  if (n > 10) {
    System.out.println("n > 10");
  } else if (n > 5) {
    System.out.println("n > 5");
  } else {
    System.out.println("n <= 5");
  }
  // 時間復雜度
  // 1 + 4 + 4 + 4
  // 14
  // O(1)

  // 空間復雜度
  // O(1)
  for (int i = 0; i < 4; i++) {
    System.out.println("test");
  }
}

public static void test2(int n) {
  // 時間復雜度
  // 1 + 3n
  // O(n)
  for (int i = 0; i < n; i++) {
    System.out.println("test");
  }
}

public static void test2(int n) {
  // 時間復雜度
  // 1 + 2n + n * (1 + 3n)
  // 1 + 2n + n  + 3n^is 2
  // 3n^2 + 3n + 1
  // O(n^2)
  for (int i = 0; i < n; i++) {
    for  (int j = 0; j < n; j++) {
      System.out.println("test");
    }
  }
}

public static void test5(int n) {
  // 時間復雜度
  // 8 = 2^3
  // 16 = 2^4
  // 3 = log2(8)
  // 16 = log2(16)
  // log2(n)
  // O(logn)
  while ((n = n / 2) > 0) {
    System.out.println("test");
  }
}

public static void test7(int n) {
  // 時間復雜度
  // 1 + 2*log2(n) + log2(n) * (1 + 3n)
  // 1 + 3*log2(n) + 2 * nlog2(n)
  // O(logn + nlogn)
  // O(nlogn)
  for (int i = 1; i < n; i = i* 2) {
    // 1 + 3n
    for  (int j = 0; j < n; j++) {
      System.out.println("test");
    }
  }
}

三、算法的優(yōu)化方向

• 用盡量少的存儲空間
• 用盡量少的執(zhí)行步驟（執(zhí)行時間）
• 根據情況，可以
  空間換時間
  時間換空間