From:     honda@luckstar.com.tw
Date:     2016-12-27
Subject:  Big-Oh 「時間複雜度」(Time complexity)

URL: 
http://svc.luckstar.com.tw/ShareAll/KM/What/Big-Oh.txt
Reference: https://market.cloud.edu.tw/content/senior/computer/ks_ks/book/algodata/algorithm/algo5.htm
https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6


----------
常見的Big-oh:

O(1)或O(c):
  稱為常數時間(constant time)
  演算法則的執行時間是一個常數，與資料集合大小變化無關。 例如: 判斷一個二進制數的奇偶.

O(n):
  稱為線性時間(linear time)
  它執行的時間會隨資料集合的大小而線性成長。例如在一個沒有排列過的資料集中找一個最大元素。

O(log(n)):
  對數時間. 例如: 二分搜索.

O(n Log(n)):
  線性對數, 或對數線性, 擬線性, 超線性.
  例如:(Heapsoft/QuickSort)排序時, 效能為(O(n log(n)), n為元素個數.

O(n^2):
  稱為平方時間(quadratic time), 例如: 冒泡排序, 插入排序.
  演算法則執行時間會成二次方的成長，這種會變得不切實際，特別是當資料集合的大小變得很大時。

O(n^3):
  稱為立方時間(cubic time). 例如: 矩陣乘法.

O(2^n):
  稱為指數時間(exponential time). 例如: 使用動態規劃解決旅行推銷員問題.