big o of n

Big o of n ==>演算法的時間複雜度
                 ==>最常用表示理論的上限



時間複雜度的等級  (最下方時間　愈久)

O(1)              常數時間  (constant time)

O(log₂ n)      次線性時間 (sub-linear)

O(n)             線性時間  (linear)

O(n log₂ n)   線性乘對數時間

O(n²)           平方時間  (quadratic)

O(n³)           立方時間  (cubic)

O(2ⁿ)           指數時間   (exponential)

O(n!)           階乘時間   (factorial)


實例  from   
from  https://ithelp.ithome.com.tw/articles/10221991

1.O(1)              常數時間  (constant time)

   陣列讀取

   

   fruits=["apple","banana","cherry","dragonfruit","elderberry","fig"]

   print(fruits[5])


2.O(log₂ n)      次線性時間 (sub-linear)
   二分搜尋法


3.O(n)             線性時間  (linear)
    簡易搜尋
   循序搜尋 (Sequential Search)

fruits=["apple","banana","cherry","dragonfruit","elderberry","fig"]
for i in range(len(fruits)):
    if fruits[i]=="fig":
        print("找到了在{}個裡".format(i+1))
        break
    else:

        print("第{}個裡找不到".format(i+1))


4.O(n log₂ n)   線性乘對數時間
   高級排序算法（合併排序 (Merge sort)、快速排序 (Quick sort)）


5.O(n²)           平方時間  (quadratic)

    簡單排序算法（選擇排序 (Selection sort)、插入排序(Insertion sort)、氣泡排序 (Bubble sort)）


6   O(n³)           立方時間  (cubic)
    Floyd 算法(動態規畫) / 矩陣乘法運算

7.   O(2ⁿ)           指數時間   (exponential)
      河內塔(動態規畫)  簡單背包問題(動態規畫)

8. O(n!)           階乘時間   (factorial)

     旅行推銷員問題 - NP