复杂度
增长曲线
Horrible |
Bad |
Fair |
Good |
Excellent |
数据结构
- 平均情况（Average Case）: 通常用 Θ (Theta) 表示。它表示在所有可能的输入情况下，算法的时间复杂度的平均值。
- 最坏情况（Worst Case）: 通常用 O (Big O) 表示。它表示在所有可能的输入情况下，算法的时间复杂度的最大值，也就是在最不利的情况下算法的表现。
| Data Structure | Access | Search | Insertion | Deletion | Space |
|---|---|---|---|---|---|
| Array | Θ(1) |
Θ(N) |
Θ(N) |
Θ(N) |
O(N) |
| Stack | Θ(N) |
Θ(N) |
Θ(1) |
Θ(1) |
O(N) |
| Queue | Θ(N) |
Θ(N) |
Θ(1) |
Θ(1) |
O(N) |
| Singly-Linked List | Θ(N) |
Θ(N) |
Θ(1) |
Θ(1) |
O(N) |
| Doubly-Linked List | Θ(N) |
Θ(N) |
Θ(1) |
Θ(1) |
O(N) |
| Skip List | Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
O(NlogN) |
| Hash Table | N/A |
Θ(1) / O(N) |
Θ(1) / O(N) |
Θ(1) / O(N) |
O(N) |
| Binary Search Tree | Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
O(N) |
| Cartesian Tree | N/A |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
O(N) |
| B-Tree | Θ(logN) |
Θ(logN) |
Θ(logN) |
Θ(logN) |
O(N) |
| Red-Black Tree | Θ(logN) |
Θ(logN) |
Θ(logN) |
Θ(logN) |
O(N) |
| Splay Tree | N/A |
Θ(logN) |
Θ(logN) |
Θ(logN) |
O(N) |
| AVL Tree | Θ(logN) |
Θ(logN) |
Θ(logN) |
Θ(logN) |
O(N) |
| KD Tree | Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
Θ(logN) / O(N) |
O(N) |
数组排序
| Algorithm | Best | Average | Worst | Space Complexity |
|---|---|---|---|---|
| Quicksort | Ω(NlogN) |
Θ(NlogN) |
O(N^2) |
O(logN) |
| Mergesort | Ω(NlogN) |
Θ(NlogN) |
O(NlogN) |
O(N) |
| Timsort | Ω(N) |
Θ(NlogN) |
O(NlogN) |
O(N) |
| Heapsort | Ω(NlogN) |
Θ(NlogN) |
O(NlogN) |
O(1) |
| Bubble Sort | Ω(N) |
Θ(N^2) |
O(N^2) |
O(1) |
| Insertion Sort | Ω(N) |
Θ(N^2) |
O(N^2) |
O(1) |
| Selection Sort | Ω(N^2) |
Θ(N^2) |
O(N^2) |
O(1) |
| Tree Sort | Ω(NlogN) |
Θ(NlogN) |
O(N^2) |
O(N) |
| Shell Sort | Ω(NlogN) |
Θ(n(logN)^2) |
O(n(logN)^2) |
O(1) |
| Bucket Sort | Ω(n+k) |
Θ(n+k) |
O(N^2) |
O(N) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Counting Sort | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort | Ω(N) |
Θ(NlogN) |
O(NlogN) |
O(N) |
复杂度分析
O(1)
n = 100
total = (n + 1) * n // 2
O(N)
通常和for循环有关
n = 100
total = 0
for i in range(n):
total += n
O(N^2)
双重循环，而且第二重j每次更新到n-1, 有回头操作(即又0开始)
for i in range(n):
for j in range(n):
print(i, j)
O(logN)
二分查找，或者和平衡二叉树相关的，因为树的高度就是logN
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Target not found
O(k^N)
常见于暴力搜索
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
O(N!)
暴力搜索中，以及全排列问题
def permute(nums):
result = []
backtrack(nums, 0, result) # 调用外部的 backtrack 函数
return result
def backtrack(nums, start, result):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # 交换
backtrack(nums, start + 1, result) # 递归生成后续排列
nums[start], nums[i] = nums[i], nums[start] # 还原交换
– END –