W tym samouczku dowiesz się, czym są notacje asymptotyczne. Dowiesz się również o notacji Big-O, notacji Theta i notacji Omega.
Wydajność algorytmu zależy od ilości czasu, pamięci i innych zasobów wymaganych do wykonania algorytmu. Wydajność mierzy się za pomocą notacji asymptotycznej.
Algorytm może nie mieć takiej samej wydajności dla różnych typów danych wejściowych. Wraz ze wzrostem rozmiaru danych wejściowych wydajność będzie się zmieniać.
Badanie zmiany działania algorytmu wraz ze zmianą kolejności wielkości wejściowej określa się jako analizę asymptotyczną.
Notacje asymptotyczne
Notacje asymptotyczne to notacje matematyczne używane do opisu czasu działania algorytmu, gdy dane wejściowe zmierzają w kierunku określonej wartości lub wartości granicznej.
Na przykład: W sortowaniu bąbelkowym, gdy tablica wejściowa jest już posortowana, czas potrzebny algorytmowi jest liniowy, czyli w najlepszym przypadku.
Ale gdy tablica wejściowa jest w odwrotnym stanie, algorytm zajmuje maksymalny czas (kwadratowy), aby posortować elementy, czyli najgorszy przypadek.
Gdy tablica wejściowa nie jest ani posortowana, ani w odwrotnej kolejności, zajmuje to średni czas. Te czasy trwania są oznaczane za pomocą notacji asymptotycznej.
Istnieją głównie trzy notacje asymptotyczne:
- Notacja Big-O
- Notacja Omega
- Notacja theta
Notacja Big-O (notacja O)
Notacja Big-O reprezentuje górną granicę czasu działania algorytmu. W ten sposób daje najgorszy przypadek złożoności algorytmu.
Big-O podaje górną granicę funkcji
O (g (n)) = (f (n): istnieją dodatnie stałe c i n 0 takie, że 0 ≦ f (n) ≦ cg (n) dla wszystkich n ≧ n 0 )
Powyższe wyrażenie można opisać jako funkcję f(n)należącą do zbioru, O(g(n))jeśli istnieje dodatnia stała ctaka, że leży pomiędzy 0i cg(n), dla dostatecznie dużego n.
Dla żadnej wartości nczas działania algorytmu nie przekracza czasu podanego przez O(g(n)).
Ponieważ podaje najgorszy możliwy czas działania algorytmu, jest szeroko stosowany do analizy algorytmu, ponieważ zawsze interesuje nas najgorszy scenariusz.
Notacja Omega (notacja Ω)
Notacja Omega reprezentuje dolną granicę czasu działania algorytmu. W ten sposób zapewnia najlepszą złożoność przypadku algorytmu.
Omega podaje dolną granicę funkcji
Ω (g (n)) = (f (n): istnieją dodatnie stałe c i n 0 takie, że 0 ≦ cg (n) ≦ f (n) dla wszystkich n ≧ n 0 )
Powyższe wyrażenie można opisać jako funkcję f(n)należącą do zbioru, Ω(g(n))jeśli istnieje dodatnia stała ctaka, że leży powyżej cg(n), dla wystarczająco dużej n.
Dla dowolnej wartości nminimalny czas wymagany przez algorytm podaje Omega Ω(g(n)).
Notacja Theta (notacja Θ)
Notacja theta obejmuje funkcję od góry i od dołu. Ponieważ reprezentuje górną i dolną granicę czasu działania algorytmu, jest używany do analizy złożoności średniej wielkości przypadku algorytmu.
Theta ogranicza funkcję w ramach stałych czynników
Dla funkcji g(n), Θ(g(n))oblicza się według zależności:
Θ (g (n)) = (f (n): istnieją dodatnie stałe c 1 , c 2 i n 0 takie, że 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) dla wszystkich n ≧ n 0 )
Powyższe wyrażenie można opisać jako funkcję f(n)należącą do zbioru, Θ(g(n))jeśli istnieją dodatnie stałe i takie, że można je umieścić pomiędzy i , dla wystarczająco dużego n.c1c2c1g(n)c2g(n)
Jeśli funkcja f(n)leży gdziekolwiek pomiędzy i dla wszystkich , to mówi się, że jest asymptotycznie ścisła.c1g(n)c2g(n)n ≧ n0f(n)
