Big O notation explain

• 參考網址：https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly
• 在電話簿找一個人的時間複雜度是 O(log n) ，因為不需要把整本電話簿遍歷一遍，我們只需要按字母順序從開頭對應，很像查英文字典的感覺。
• 電話簿範例延伸，現在假設電話簿裡面有企業與人的電話，企業的名字是唯一的、人的名字不唯一：
  • O(1) (best case)：給定企業名字所在的頁面，找到企業的電話。
  • O(1) (average case)：給定人的名字所在的頁面，找到人的電話。
  • O(log n)：給定人的名字，請找到人的電話。（類似binary search）
  • O(n)：找到電話號碼有5的所有人。
  • O(n)：給定一個電話號碼，找到一個人或企業是那個號碼。
  • O(n log n)：電話簿的頁面亂掉了，通過查看電話簿頁面的第一個名字來重新排序電話簿。
• 範例再次延伸，現在影印店有一堆電話簿，那些電話簿上有貼貼紙說要寄到哪個人或公司。
  • O(n log n)：我們想個人化那些電話簿，幫每本電話簿的主人圈出他們的電話。
  • O(n^2)：影印店出了一點問題，每一本電話簿上的電話號碼都有多餘的0，請拿立可白把它塗掉。
  • O(n · n!)：電話簿準備裝櫃放到碼頭了，但是負責搬運的機器人故障，只會隨機的把電話簿放進貨櫃，然後檢查是否排序正確，有錯誤就會全部拿出來，重新放進貨櫃。（Bogo Sort、猴子排序、無限猴子定理）
  • O(n^n)：搬運機器人目前是正常的，但是同事給妳惡作劇，多加了機器人路徑每次搬運完都會自動列印機去印東西，一但機器人拿了一本電話簿，自動列印機就會印所有重複的電話簿，幸運的事，這機器人有不錯的錯誤處理，當他搬到重複的電話簿，他就不會使用自動列印機了，但他還是需要去裝載每一本原始及重複的電話簿。