Główna zawartość

Podstawy informatyki - program rozszerzony

Kurs: Podstawy informatyki - program rozszerzony > Jednostka 4

Lekcja 2: Ocena złożoności algorytmów

Klasyfikacja efektywności czasu pracy

Zrozumienie czasu wykonywania używanych przez nas algorytmów jest bardzo ważne. Gdy komputerowi zbyt długo zajmuje rozwiązanie problemu, kosztuje to więcej pieniędzy i pozbawia go czasu, który może poświęcić na inne wartościowe problemy. Ponadto, jeśli algorytm jest używany w aplikacji skierowanej do użytkownika, może to doprowadzić do frustracji użytkowników, którzy całkowicie zrezygnują z korzystania z aplikacji.

Kategoryzacja czasów wykonywania

Czas wykonania algorytmu można podzielić na kategorie w zależności od tego, jak zwiększa się liczba kroków w miarę zwiększania rozmiaru danych wejściowych. Czy zawsze trwa to tyle samo czasu? Jest to stały wzrost, czyli bardzo szybki czas wykonywania. Czy algorytm zawsze wymaga przeanalizowania każdej możliwej permutacji danych wejściowych? Jest to wzrost wykładniczy, czyli bardzo wolny czas wykonywania. Większość czasów wykonania znajduje się gdzieś pomiędzy.

Stały czas

Gdy algorytm wykonuje się w stałym czasie, oznacza to, że zawsze wykonuje stałą liczbę kroków, niezależnie od tego, jak duży jest rozmiar danych wejściowych.

Jako przykład rozważmy dostęp do pierwszego elementu listy:

firstPost ← posts[1]

Nawet jeśli lista zwiększy się do miliona elementów, operacja ta zawsze będzie wymagała wykonania jednego kroku.

Relację tę można zobrazować w postaci tabeli:

Rozmiar listy	Kroki
1	1
10	1
100	1
1000	1

Można to również przedstawić w postaci wykresu:

Idealnym rozwiązaniem jest stały czas wykonywania, ale zazwyczaj nie jest to możliwe w przypadku algorytmów przetwarzających wiele fragmentów danych.

Czas logarytmiczny

Gdy algorytm wykonuje się w czasie logarytmicznym, jego czas rośnie proporcjonalnie do logarytmu rozmiaru danych wejściowych.

Algorytm wyszukiwania binarnego jest algorytmem wykonującym się w czasie logarytmicznym. Szczegółowe wyjaśnienie działania tego algorytmu można znaleźć w artykule poświęconym pomiarom wydajności.

Oto pseudokod:

PROCEDURE searchList(numbers, targetNumber) {
  minIndex ← 1
  maxIndex ← LENGTH(numbers)
  REPEAT UNTIL (minIndex > maxIndex) {
    middleIndex ← FLOOR((minIndex+maxIndex)/2)
    IF (targetNumber = numbers[middleIndex]) {
      RETURN middleIndex
    } ELSE {
       IF (targetNumber > numbers[middleIndex]) {
         minIndex ← middleIndex + 1
       } ELSE {
         maxIndex ← middleIndex - 1
       }
     }
  }
  RETURN -1
}

Algorytm wykorzystuje pętlę do sprawdzenia wielu elementów listy, ale co istotne, nie sprawdza każdego elementu listy. W szczególności przegląda log, start base, 2, end base, n elementów, gdzie n jest liczbą elementów na liście.

Zależność tę można przedstawić za pomocą tabeli:

Rozmiar listy	Kroki
1	1
10	4
100	7
1000	10

Można to również przedstawić w postaci wykresu:

Liczba kroków zdecydowanie rośnie wraz ze wzrostem rozmiaru danych wejściowych, ale w bardzo powolnym tempie.

Czas liniowy

Gdy algorytm rośnie w czasie liniowym, liczba jego kroków rośnie wprost proporcjonalnie do wielkości danych wejściowych.

Algorytm o trafnej nazwie "wyszukiwanie liniowe" wykonuje się w czasie liniowym.

Pseudokod pokazuje jego prostotę w porównaniu z wyszukiwaniem binarnym:

PROCEDURE searchList(numbers, targetNumber) {
  index ← 1
  REPEAT UNTIL (index > LENGTH(numbers)) {
    IF (numbers[index] = targetNumber) {
      RETURN index
    }
    index ← index + 1
  }
  RETURN -1
}

Tym razem pętla sprawdza każdy element listy. Takie pełne przeszukiwanie jest niezbędne do wyszukiwania elementów na nieposortowanej liście, ponieważ nie ma sposobu na zawężenie miejsca, w którym dany element może się znajdować. Ten algorytm zawsze będzie wymagał co najmniej tylu kroków, ile jest elementów na liście.

Możemy to zobaczyć w formie tabeli:

Rozmiar listy	Kroki
1	1
10	10
100	100
1000	1000

Lub w formie wykresu:

Czas kwadratowy

Gdy algorytm rośnie w czasie kwadratowym, jego liczba kroków rośnie proporcjonalnie do kwadratu wielkości danych wejściowych.

Kilka algorytmów sortowania listy wykonuje się w czasie kwadratowym, na przykład sortowanie przez wybieranie. Algorytm ten zaczyna od początku listy, a następnie znajduje kolejną najmniejszą wartość na liście i zamienia ją z wartością bieżącą.

Oto pseudokod do sortowania przez wybieranie:

i ← 1
REPEAT UNTIL (i > LENGTH(numbers)) {
  minIndex ← i
  j ← i + 1
  // Find next smallest value
  REPEAT UNTIL (j > LENGTH(numbers)) {
    IF (numbers[j] < numbers[minIndex]) {
      minIndex ← j
    }
  }
  // Swap if new minimum found
  IF (minIndex != i) {
    tempNum ← numbers[minIndex]
    numbers[i] ← tempNum
    numbers[minIndex] <- tempNum
  }
}

Ważną rzeczą, którą należy zauważyć w algorytmie, jest zagnieżdżona pętla: pętla przechodzi przez każdy element listy, a następnie ponownie przez pozostałe elementy dla każdego z tych elementów. W tym przypadku algorytm sprawdza start fraction, 1, divided by, 2, end fraction, left parenthesis, n, squared, minus, n, right parenthesis wartości, gdzie n to liczba pozycji na liście.

W tabeli przedstawiono liczbę elementów, które należałoby sprawdzić w przypadku list o coraz większych rozmiarach:

Rozmiar listy	Kroki
1	1
10	45
100	4950
1000	499500

Oto, jak to wygląda w formie wykresu:

Zarówno z tabeli, jak i z wykresu wynika, że liczba kroków dla tego algorytmu rośnie znacznie szybciej niż dla poprzednich.

Czas wykładniczy

Gdy algorytm rośnie w czasie ponadwielomianowym, liczba jego kroków rośnie szybciej niż wielomianowa funkcja rozmiaru danych wejściowych.

Algorytm często wymaga ponadwielomianowego czasu, gdy musi przeanalizować każdą permutację wartości. Na przykład, rozważmy algorytm generujący wszystkie możliwe hasła numeryczne dla zadanej długości hasła.

Dla hasła o długości 2 generuje 100 haseł:

0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59  
60 61 62 63 64 65 66 67 68 69  
70 71 72 73 74 75 76 77 78 79  
80 81 82 83 84 85 86 87 88 89  
90 91 92 93 94 95 96 97 98 99

Ten algorytm wymaga co najmniej 10, squared kroków, ponieważ dla każdej cyfry (0-9) istnieje 10 możliwości i musi wypróbować każdą możliwość dla każdej z 2 cyfr.

Dla hasła o dowolnej długości n algorytm wymaga 10, start superscript, n, end superscript kroków. Czas ten rośnie niewiarygodnie szybko, ponieważ każda dodatkowa cyfra wymaga 10-krotnie większej liczby kroków.

Ta tabela pokazuje, jak szybko rośnie liczba dla pierwszych pięciu cyfr:

Cyfry	Kroki
1	10
2	100
3	1000
4	10000
5	100000

Oto jak to wygląda w formie wykresu:

Wszystkie czasy wykonania w jedynym miejscu

Teraz, gdy poznaliśmy przykłady możliwych czasów wykonania dla algorytmów, porównajmy je na wykresie:

Wykres ten jeszcze wyraźniej pokazuje, że istnieje wyraźna różnica w tych czasach wykonywania, zwłaszcza gdy zwiększa się rozmiar danych wejściowych. Ponieważ nowoczesne programy komputerowe coraz częściej mają do czynienia z dużymi zbiorami danych (np. pochodzącymi od milionów użytkowników lub czujników), wydajność czasowa ma duże znaczenie.

Wielomiany i ponadwielomiany

Informatycy często dzielą czasy wykonania na dwie klasy:

Czas wielomianowy opisuje dowolny czas działania, który nie rośnie szybciej niż n, start superscript, k, end superscript, co obejmuje złożoność stałą (n, start superscript, 0, end superscript), złożoność logarytmiczną (log, start base, 2, end base, n), złożoność liniową (n, start superscript, 1, end superscript), złożoność kwadratową (n, squared) i inne wielomiany wyższych stopni (jak n, cubed).
Czas ponadwielomianowy opisuje każdy czas działania, który rośnie szybciej niż n, start superscript, k, end superscript, i obejmuje złożoność wykładniczą (2, start superscript, n, end superscript), złożoność typu silnia (n, !) i wszystko, co szybsze.

Dlaczego dokonujemy podziału na wielomian i ponadwielomiany?

Poniższa tabela zawierająca czasy wykonania ilustruje dlaczego:

	10	50	100	300	1000
5, n	50	250	500	1500	5000
n, squared	100	2500	10000	90000	$\text{1 million} \\\\ \text{(7 digits)}$
n, cubed	1000	125000	$\text{1 milion} \\\\ \text{(7 cyfr)}$	$\text{27 milionów} \\\\ \text{(8 cyfr)}$	$\text{1 miliard} \\\\ \text{(10 cyfr)}$
2, start superscript, n, end superscript	1024	$\text{16-cyfrowa} \\\\ \text{liczba}$	$\text{31-cyfrowa} \\\\ \text{liczba}$	$\text{91-cyfrowa} \\\\ {\text{liczba}}$	$\text{302-cyfrowa} \\\\ \text{liczba}$
n, !	$\text{3.6 million} \\\\ \text{(7 cyfr)}$	$\text{65-cyfrowa} \\\\ {\text{liczba}}$	$\text{161-cyfrowa} \\\\ {\text{liczba}}$	$\text{623-cyfrowa} \\\\ {\text{liczba}}$	$\text{niewyobrażalnie} \\\\ {\text{duża liczba}}$

Liczby te nie mają jednostek, więc algorytm n, ! może działać w ciągu 3,6 miliona nanosekund dla n równego 10, co jest mniej niż sekundą. Dla n równego 50, algorytm będzie wykonywał się przez 3, times, 10, start superscript, 64, end superscript nanosekund, ale od Wielkiego Wybuchu upłynęło tylko 10, start superscript, 26, end superscript nanosekund! Ponadwielomianowy czas działania często wymaga więcej czasu, niż jest dostępne we wszechświecie, nawet dla stosunkowo niewielkich rozmiarów danych wejściowych.

Dlatego wielomianowe czasy obliczeń uważamy za rozsądne, a ponadwielomiany za nierozsądne. Wielomianowy czas wykonania nie zawsze jest idealny (i często staramy się go poprawić), ale jest przynajmniej wykonalny.

Informatycy koncentrują swoje wysiłki na znalezieniu algorytmów wielomianowych dla problemów, które obecnie wymagają czasu ponadwielomianowego, ponieważ właśnie tam różnica ma największe znaczenie.

Kolejne lektury

"Analiza asymptotyczna" to bardziej formalna metoda analizy efektywności algorytmów. Nie jest ona tutaj omawiana, ale jeśli jesteś zainteresowany, możesz dowiedzieć się więcej na temat analizy asymptotycznej z naszego kursu o algorytmach na poziomie szkoły wyższej.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Czy masz jakieś pytania na ten temat? Chętnie na nie odpowiemy — wystarczy, że zadasz pytanie w poniższym obszarze pytań!

[Gdzie mogę to znaleźć?]

Sortuj według

Chcesz dołączyć do dyskusji?

Zaloguj się

Na razie brak głosów w dyskusji

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.