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ść

Asymptotyczne tempo wzrostu

Jak na razie analizowaliśmy wyszukiwanie liniowe i binarne poprzez liczenie ilości maksymalnych prób, które musimy wykonać. Lecz to, co chcemy tak naprawdę wiedzieć to, jak długo się wykonuje. Jesteśmy zainteresowani czasem wykonania, nie tylko ilością prób. Czas wykonania wyszukiwania liniowego oraz binarnego obejmuje czas poświęcony na wykonanie i sprawdzenie każdej próby, oprócz tego związany jest jeszcze z czymś więcej niż tylko z tymi czynnościami.
Czas wykonania algorytmu zależy od tego, jak szybko komputer jest w stanie wykonać instrukcje, zawarte w kodzie danego algorytmu. A to zależy od szybkości komputera, języka programowania oraz kompilatora, który tłumaczy program z języka programowania na kod, który wykonywany jest bezpośrednio na komputerze jak również innych czynników.
Przyjrzyjmy się czasowi wykonania algorytmu bardziej dokładnie. Po pierwsze, określmy jak długo wykonuje się algorytm w odniesieniu do rozmiaru danych wejściowych. Ta koncepcja jest dość intuicyjna, nieprawdaż? Już wiemy, że maksymalna liczba prób w wyszukiwaniach liniowym oraz binarnym zwiększa się wraz ze wzrostem długości przeszukiwanej tablicy. Pomyśl sobie o systemie GPS. Jeśli znałby tylko o autostrady, a nie każdą najmniejszą drogę, wyznaczenie trasy byłoby znacznie szybsze, prawda? Więc o czasie wykonania algorytmu myślimy, jako funkcji wielkości danych wejściowych.
Druga ważna idea polega na tym, że skupiamy się na pytaniu, jak szybko funkcja ta rośnie wraz ze wzrostem wielkości danych wejściowych. Mówimy na to tempo wzrostu czasu wykonania. Aby móc wykonać obliczenie, upraszczamy badaną funkcję, by wydobyć z niej najważniejsze elementy, odrzucając te mniej istotne. Załóżmy, na przykład, że algorytm działa na rozmiarze danych wejściowych wynoszącym n, i wówczas zajmie mu to 6n2+100n+300 instrukcji maszynowych. Wyraz 6n2 zaczyna gwałtownie rosnąć, gdy staje się większy od 100n+300, to znaczy, gdy n=20). Poniżej znajduje się wykres przedstawiający wartości dla 6n2 oraz 100n+300 dla n od 0 do 100.
Mówimy, że czas działania tego algorytmu rośnie jak n2, pomijając współczynnik 6 oraz pozostałe wyrażenia 100n+300. Tak naprawdę nie ma to znaczenia, jakich współczynników używamy; tak długo jak czas wykonania wynosi an2+bn+c, dla niektórych liczb a>0, b oraz c zawsze będą wartością n, dla których an2 jest większe niż bn+c i ta różnica zwiększa się wraz ze wzrostem n. Na przykład, poniżej znajduje się wykres ilustrujący wartości dla 0,6n2 oraz 1000n+3000, gdzie dokonaliśmy redukcji współczynnika n2 10-krotnie natomiast pozostałe dwie stałe zwiększyliśmy 10-krotnie.
Wartość n, przy którym 0,6n2 staje się większe od 1000n+3000 wzrosła, ale zawsze znajdzie się punkt przecięcia bez względu na to, jakie przyjęte stałe.
Dzięki pominięciu mniej znaczących wyrażeń i stałych współczynników, możemy skupić się tej części algorytmu, która w największym stopniu wpływa na czas jego wykonania – jest to tempo wzrostu – bez pogrążania się w szczegóły, które utrudniają jego zrozumienie. Kiedy pomijamy stałe współczynniki oraz mniej znaczące wyrażenia, używamy notacji asymptotycznej. Zapoznamy się z jej trzema postaciami: notacja duże-Θ, notacja duże-O oraz notacja duże-Ω.
Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormen i Devina Balkcom oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.

Chcesz dołączyć do dyskusji?

  • Awatar starky tree style dla użytkownika Paweł Woliński
    "Załóżmy, na przykład, że algorytm działa na rozmiarze danych wejściowych wynoszącym n, wówczas zajmie mu to 6n²+100n+300 instrukcji maszynowych."
    Szczerze nie rozumiem genezy tych liczb, dlaczego 6n² i co oznaczają oraz skąd się wzięły te współczynniki.
    Z góry dziękuję za odpowiedź.
    (1 głos)
    Awatar Default Khan Academy avatar dla użytkownika
    • Awatar mr pink red style dla użytkownika Andrzej
      To całe zdanie to jest założnie. Powinno być "Załóżmy, że algorytm który działa na rozmiarze danych wejściowych wynoszących n, wykonuję BLABLABLA instrukcji."

      Sprawdziłem, z angielską wersją i to zwykły problem z tłumaczeniem, już zgłosiłem do poprawki.
      (6 głosów)
  • Awatar blobby green style dla użytkownika kacpergrunau97
    ile to jest 2*100-50+4000*3:9?
    (0 głosów)
    Awatar Default Khan Academy avatar dla użytkownika
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.