Linux中國
每個程序員都應該收藏的演算法複雜度速查表
圖例
| 絕佳 | 不錯 | 一般 | 不佳 | 糟糕 |
數據結構操作
| 數據結構 | 時間複雜度 | 空間複雜度 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 平均 | 最差 | 最差 | |||||||
| 訪問 | 搜索 | 插入 | 刪除 | 訪問 | 搜索 | 插入 | 刪除 | ||
| Array | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash Table | - | O(1) | O(1) | O(1) | - | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(n) | O(n) | O(n) | O(n) |
| B-Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Red-Black Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
數組排序演算法
| 演算法 | 時間複雜度 | 空間複雜度 | ||
|---|---|---|---|---|
| 最佳 | 平均 | 最差 | 最差 | |
| Quicksort | O(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) |
| Mergesort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Timsort | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Shell Sort | O(n) | O((nlog(n))^2) | O((nlog(n))^2) | O(1) |
| [Bucket Sort](http://en.wikipedia.org/wiki/Bucket_sort "Only for integers. k is a number of buckets") | O(n+k) | O(n+k) | O(n^2) | O(n) |
| [Radix Sort](http://en.wikipedia.org/wiki/Radix_sort "Constant number of digits 'k'") | O(nk) | O(nk) | O(nk) | O(n+k) |
圖操作
| 節點 / 邊界管理 | 存儲 | 增加頂點 | 增加邊界 | 移除頂點 | 移除邊界 | 查詢 | ||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Adjacency list | O( | V | + | E | ) | O(1) | O(1) | O( | V | + | E | ) | O( | E | ) | O( | V | ) | ||||||||||
| Incidence list | O( | V | + | E | ) | O(1) | O(1) | O( | E | ) | O( | E | ) | O( | E | ) | ||||||||||||
| Adjacency matrix | O( | V | ^2) | O( | V | ^2) | O(1) | O( | V | ^2) | O(1) | O(1) | ||||||||||||||||
| Incidence matrix | O( | V | ⋅ | E | ) | O( | V | ⋅ | E | ) | O( | V | ⋅ | E | ) | O( | V | ⋅ | E | ) | O( | V | ⋅ | E | ) | O( | E | ) |
堆操作
| 類型 | 時間複雜度 | ||||||
|---|---|---|---|---|---|---|---|
| Heapify | 查找最大值 | 分離最大值 | 提升鍵 | 插入 | 刪除 | 合併 | |
| Linked List (sorted) | - | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |
| Linked List (unsorted) | - | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) |
| Binary Heap | O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) |
| Binomial Heap | - | O(1) | O(log(n)) | O(log(n)) | O(1) | O(log(n)) | O(log(n)) |
| Fibonacci Heap | - | O(1) | O(log(n)) | O(1) | O(1) | O(log(n)) | O(1) |
大 O 複雜度圖表
推薦閱讀
- Cracking the Coding Interview: 150 Programming Questions and Solutions
- Introduction to Algorithms, 3rd Edition
- Data Structures and Algorithms in Java (2nd Edition)
- High Performance JavaScript (Build Faster Web Application Interfaces)
貢獻者
- Eric Rowell, creator of Concrete.js, an HTML5 Canvas Framework
- Quentin Pleple
- Michael Abed
- Nick Dizazzo
- Adam Forsyth
- David Dorfman
- Jay Engineer
- Jennifer Hamon
- Josh Davis
- Nodir Turakulov
- Bart Massey
- Vinnie Magro
- Miguel Amigot
- Drew Bailey
- Aneel Nazareth
- Rahul Chowdhury
- Robert Burke
- steven41292
- Brandon Amos
- Mike Davis
- Casper Van Gheluwe
- Joel Friedly
- Oleg
- Renfred Harper
- Piper Chester
- Eric Lefevre-Ardant
- Jonathan McElroy
- Si Pham
- mcverry
- Max Hoffmann
- Alejandro Ramirez
- Damon Davison
- Alvin Wan
- Alan Briolat
- Drew Hannay
- Andrew Rasmussen
- Dennis Tsang
- Bahador Saket
本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive
對這篇文章感覺如何？
太棒了
0
不錯
0
愛死了
0
不太好
0
感覺很糟
0
You may also like
More in:Linux中國
如何通過 VLC 使用字幕
使用 VLC 媒體播放器播放和管理字幕的新手指南。
Unix 桌面：在 Linux 問世之前
僅僅開源還不足以實現開放，還需開放標準和建立共識。
Valve 對於 Ubuntu 的 Snap 版本的 Steam 並不滿意：原因何在
你可能會發現，Snap 版本的 Steam 並不如你期待的那樣好，你怎麼看？
Wine 9.0 發布，實驗性地加入了 Wayland 驅動
Wine 的這個新版本正在為未來做好準備！
關注 LinuxStory 微信公眾號，獲取最新的 Linux 和操作系統資訊，每天為您帶來熱騰騰的開源新聞與新鮮溫暖的科技故事。
