Efektywność algorytmów

Dwa algorytmy mogą dać ten sam wynik, ale w bardzo różnym czasie. Efektywność mierzymy liczbą operacji potrzebnych dla danych o rozmiarze n.

Wyszukiwanie liniowe sprawdza po kolei wszystkie elementy — dla miliona danych to milion kroków. Wyszukiwanie binarne w posortowanym zbiorze potrzebuje około dwudziestu.

Podobnie z sortowaniem: metody proste wykonują około n do kwadratu porównań, a szybkie algorytmy znacznie mniej. Przy dużych danych ta różnica decyduje o użyteczności programu.

• n — rozmiar danych wejściowych
• liniowe — około n kroków
• binarne — około log n kroków
• 1 000 000 — milion danych: 20 kroków binarnie
• n do kwadratu — koszt prostego sortowania

• Wyszukiwanie liniowe — sprawdza kolejno wszystko
• Wyszukiwanie binarne — dzieli zbiór na pół
• Sortowanie bąbelkowe — proste, ale wolne
• Sortowanie szybkie — dużo wydajniejsze dla dużych zbiorów

Co oznacza n w analizie algorytmu?

Rozmiar danych wejściowych.

Ile kroków ma wyszukiwanie liniowe?

W najgorszym razie tyle, ile elementów.

Jaki warunek ma wyszukiwanie binarne?

Dane muszą być posortowane.

Ile kroków binarnie dla miliona elementów?

Około dwudziestu.

Dlaczego sortowanie bąbelkowe jest wolne?

Wykonuje około n do kwadratu porównań.

Kiedy różnica w efektywności ma znaczenie?

Przy dużych zbiorach danych.

Co robi wyszukiwanie binarne w każdym kroku?

Odrzuca połowę pozostałych elementów.

Czy szybszy komputer zastąpi lepszy algorytm?

Nie przy dużych danych — wzrost kosztu jest zbyt szybki.

Ile porównań wymaga w najgorszym razie wyszukiwanie liniowe w liście tysiąca elementów?

Tysiąc — sprawdzamy każdy element po kolei.

Jak zmienia się czas algorytmu kwadratowego po podwojeniu danych?

Wydłuża się mniej więcej czterokrotnie.

Kiedy sortowanie bąbelkowe w zupełności wystarcza?

Przy małych zbiorach, na przykład kilkunastu elementach.

Co oznacza algorytm o stałej liczbie kroków?

Że działa tak samo szybko niezależnie od rozmiaru danych.

1. W każdym kroku wyszukiwanie binarne odrzuca:

1. Jeden element
2. Połowę elementów
3. Wszystkie
4. Nic

2. Efektywność algorytmu mierzymy:

1. Długością kodu
2. Liczbą operacji dla n danych
3. Liczbą zmiennych
4. Kolorem edytora

3. Podwojenie liczby danych w algorytmie liniowym…

1. Nie zmienia czasu
2. Mniej więcej podwaja czas
3. Czterokrotnie wydłuża czas
4. Skraca czas

4. Algorytm o stałej liczbie kroków…

1. Zwalnia przy większych danych
2. Działa tak samo szybko niezależnie od rozmiaru danych
3. Wymaga sortowania
4. Nie istnieje

5. Wyszukiwanie binarne ma złożoność:

1. liniową
2. logarytmiczną
3. kwadratową
4. stałą