Rząd wielkości służy do opisu czasu działania algorytmu. Istnieją 3 notacje służące do tego celu.
1. Notacja O (omikron).
Jest to ograniczenie funkcji od góry. Gdy mówimy, że pewna f(n) funkcja jest rzędu g(n), co zapisujemy f(n)=O(g(n)), znaczy to, że istnieje taki argument n₀, od którego począwszy dla każdego niemniejszego od n₀ wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnościądo stałej c. Brzmi to trochę skomplikowanie, więc zademonstruję to na przykładzie:

Na prawo od punktu od n₀ funkcja f(n) znajduje się pod funkcją c^.g(n), czyli jest przez nią ograniczona z góry.
Jest to asymptotyczna granica górna. Służy do szacowania czasu działania algorytmu w przypadku pesymistycznym.
2. Notacja Θ (theta)
Notacja ta ogranicza funkcję f(n) od góry, tak jak notacja O oraz dodatkowo od dołu. Oznacza to, że jeżeli f(n)=Θ(g(n)) to istnieje taki argument n₀, od którego począwszy dla każdego argumenu od niego niemniejszego:

• wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnościądo stałej c₁
• wartości funkcji f(n) są niemniejsze od wartości funkcji g(n) z dokładnościądo stałej c₂

I znów przykład:

Na prawo od punktu od n₀ funkcja f(n) znajduje się pod funkcją c₁^.g(n), czyli jest przez nią ograniczona z góry i nad funkcją c₂^.g(n), czyli jest przez nią ograniczona z dołu
Jest to asymptotyczne oszacowanie dokładne.
3. Notacja Ω (omega).
Notacja ta ogranicza funkcję f(n) od dołu. Oznacza to, że jeśli f(n)=Ω(g(n)) to istnieje taki argument n₀, od którego począwszy dla każdego argumenu od niego niemniejszego funkcja f(n) jest niemniejsza niż g(n) z dokładnościądo stałej c:

Na prawo od punktu od n₀ funkcja f(n) znajduje się nad funkcją c^.g(n). Jest to asymptotyczna granica dolna. Służy więc do oszacowania działania algorytmu w najlepszym przypadku.
Zobacz też złożoność obliczeniowa

Komentarze