L2 演算法复杂性与问题下界

渐进符号

• f(n) = O(g(n)):最多
  • |f(n)| <= c|g(n)|
• f(n) = Ω(g(n)):最少
  • |f(n)| >= c|g(n)|
• f(n) = Θ(g(n))
  • c1|g(n)| <= |f(n)| <= c2|g(n)|

比较

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

演算法比较

Straight Insertion Sort

• best case:O(n)
• worst case:O(n^2)
• average case:O(n^2)
• 

Binary Search

• best case:O(1)
• worst case:O(log n)
• average case:O(log n)
• 

Selection Sort

• best case:O(n)
• worst case:O(n^2)
• average case:O(nlog n)
• 

Quick Sort

• best case:O(nlog n)
• worst case:O(n^2)
• average case:O(nlog n)
•