演算法的時間與空間效率

電腦科學的核心概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Big-O 記號入門

  • 隨輸入成長衡量時間與空間成長
  • 例：$O(n)$、$O(n^2)$、$O(log\, n)$
  • 「O」表示成長「階」，如 O(n)＝線性
電腦科學的核心概念

時間複雜度－辦公室類比

顯示各種 Big O 複雜度的圖表

  • $O(1)$－常數時間－「快速一瞥」－「constant」
  • $O(log\,n)$－時間緩增－「堆疊對分」－「logarithmic」
  • $O(n)$－線性成長－「逐頁閱讀」－「linear」
  • $O(n\,log\,n)$－成長較快－「成堆排序」－「linearithmic」
  • $O(n^2)$－平方時間－「成對比對」－「quadratic」
電腦科學的核心概念

空間複雜度－辦公室類比

顯示各種 Big O 複雜度的圖表

  • $O(1)$－常數空間－「桌面空間」－「constant」
  • $O(log\,n)$－空間緩增－「極簡筆記」－「logarithmic」
  • $O(n)$－線性成長－「便條紙」－「linear」
  • $O(n\,log\,n)$－成長較快－「臨時紙堆」－「linearithmic」
  • $O(n^2)$－平方空間－「比對格」－「quadratic」
電腦科學的核心概念

一起來練習吧！

電腦科學的核心概念

Preparing Video For Download...