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)