If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Funkcje w notacji asymptotycznej

Kiedy używamy notacji asymptotycznej w celu zobrazowania tempa wzrostu czasu wykonywania algorytmu, wyrażanego wielkością zmiennej wejściowej n, warto mieć kilka rzeczy na uwadze.
Zacznijmy od czegoś prostego. Załóżmy, że algorytm potrzebuje stałą ilość czasu, niezależnie od wielkości zmiennej wejściowej. Na przykład, jeżeli otrzymałeś tablicę, która jest już posortowana w kolejności rosnącej i trzeba by znaleźć minimalny element, zajęłoby to stałą ilość czasu, ponieważ minimalny element musi być pod indeksem 0. Z uwagi na to, że chcemy wykorzystać funkcję zmiennej n w notacji asymptotycznej, można powiedzieć, że ten algorytm działa w Θ(n0) czasie. Dlaczego? Ponieważ n0=1 i czas działania algorytmu mieści się w zakresie stałej 1. W praktyce, nie piszemy Θ(n0), ale Θ(1).
Załóżmy, że czas, potrzebny na wykonanie algorytmu można szacować jako Θ(log10n). Możemy również powiedzieć, że czas był Θ(log2n). Jak długo podstawa logarytmu jest stałą, nie ma znaczenia jakiej podstawy użyjemy w notacji asymptotycznej. Dlaczego nie? Ponieważ istnieje następujący wzór matematyczny:
logan=logbnlogba
dla wszystkich liczb dodatnich a,b oraz n. W związku z tym, jeżeli a i b są stałymi, to logan i logbn różnią się tylko współczynnikiem logba, i jest to wspóczynnik, który możemy pominąć w notacji asymptotycznej.
Możemy zatem powiedzieć, że w najgorszym wypadku, czas wykonywania algorytmu wyszukiwania binarnego to Θ(logan) dla każdej dodatniej stałej a. Dlaczego? Liczba prób to co najwyżej log2n+1, generowanie i testowanie każdej próby zabiera stałą ilość czasu, i definiowanie oraz zwracanie zajmuje również stałą ilość czasu. W praktyce piszemy, że wyszukiwanie binarne zajmuje Θ(log2n) czasu ponieważ informatycy lubią myśleć w kategoriach potęgi z 2.
Dla funkcji, których często używamy podczas analizy algorytmów używając notacji asymptotycznej istnieje pewien porządek. Jeżeli a oraz b są stałe i a<b, wtedy czas wykonania wynosi Θ(na) rośnie wolniej niż czas wykonania Θ(nb). Na przykład, czas wykonania Θ(n), który wynosi Θ(n1), rośnie wolniej niż czas wykonania Θ(n2). Wykładniki nie muszą nawet być liczbami całkowitymi. Na przykład, czas wykonania Θ(n2) rośnie wolniej niż czas wykonania Θ(n2n), który wynosi Θ(n2.5).
Na poniższym wykresie porównano tempo wzrostu n,n2, oraz n2,5:
Wykres porównujący tempo wzrostu n, n do kwadratu, oraz n do potęgi 2,5
Logarytmy rosną wolniej niż wielomiany. Oznacza to, że Θ(log2n) rośnie wolniej niż Θ(na) dla każdej dodatniej stałej a. Ale ponieważ wartość log2n zwiększa się ze wzrostem n, Θ(log2n) rośnie szybciej niż Θ(1).
Na poniższym wykresie porównano tempo wzrostu 1,n, oraz log2n:
Porównanie funkcji stałej równej 1, logarytmu o podstawie 2 z n, oraz n
Oto lista funkcji w notacji asymptotycznej, z którymi mamy często do czynienia podczas analizowania algorytmów, w kolejności od najwolniej do najszybciej rosnących.
  1. Θ(1)
  2. Θ(log2n)
  3. Θ(n)
  4. Θ(nlog2n)
  5. Θ(n2)
  6. Θ(n2log2n)
  7. Θ(n3)
  8. Θ(2n)
  9. Θ(n!)
Należy zauważyć, że funkcja wykładnicza an, gdzie a>1, rośnie szybciej niż jakakolwiek funkcja wielomianowa nb, gdzie b jest stałą.
Ta lista nie jest oczywiście pełna, jest wiele funkcji, które opisują złożoności obliczeniowe czy czasy wykonania różne od tych powyżej. Zapewne napotkasz niektóre z nich w swojej podróży przez krainę informatyki.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.