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

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 listyKroki
11
101
1001
10001
Można to również przedstawić w postaci wykresu:
A line graph with an x axis of 0 to 1000 and a y axis of 0 to 20. Points are plotted at (1, 1), (10, 1), (100, 1), and (1000, 1). Lines are connecting the points.
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 listyKroki
11
104
1007
100010
Można to również przedstawić w postaci wykresu:
A line graph with an x axis of 0 to 1000 and a y axis of 0 to 20. Points are plotted at (1, 1), (10, 4), (100, 7), and (1000, 10). A curved line connects the points.
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 listyKroki
11
1010
100100
10001000
Lub w formie wykresu:
A line graph with an x axis of 0 to 1000 and a y axis of 0 to 1000. Points are plotted at (1, 1), (10, 10), (100, 100), and (1000, 1000). A straight line connects the points.

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 listyKroki
11
1045
1004950
1000499500
Oto, jak to wygląda w formie wykresu:
A line graph with an x axis of 0 to 1000 and a y axis of 0 to 600,000. Points are plotted at (1, 1), (10, 45), (100, 4950), and (1000, 499500). A curved line goes through the points.
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:
CyfryKroki
110
2100
31000
410000
5100000
Oto jak to wygląda w formie wykresu:
A line graph with an x axis of 0 to 50 and a y axis of 0 to 100,000. Points are plotted at (1, 10), (2, 100), (3, 1000), (4, 10000), and (5, 100000). A curved line goes through the points.

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:
A graph with an x axis of 0 to 20 and a y axis of 0 to 30. 5 lines are plotted on the graph, each with different labels and shapes. A straight line goes across the bottom of the graph, where y is 1, and is labeled "1". A curved line grows very slowly across the bottom of the graph and is labeled "log2(n)". A straight line goes diagonally across the graph and is labeled "n". A curved line grows quickly and is labeled "n^2". Another curved line grows even more quickly and is labeled "10^n".
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:
10501003001000
5, n5025050015005000
n, squared100250010000900001 million(7 digits)\text{1 million} \\\\ \text{(7 digits)}
n, cubed10001250001 milion(7 cyfr)\text{1 milion} \\\\ \text{(7 cyfr)}27 milionoˊw(8 cyfr)\text{27 milionów} \\\\ \text{(8 cyfr)}1 miliard(10 cyfr)\text{1 miliard} \\\\ \text{(10 cyfr)}
2, start superscript, n, end superscript102416-cyfrowaliczba\text{16-cyfrowa} \\\\ \text{liczba}31-cyfrowaliczba\text{31-cyfrowa} \\\\ \text{liczba}91-cyfrowaliczba\text{91-cyfrowa} \\\\ {\text{liczba}}302-cyfrowaliczba\text{302-cyfrowa} \\\\ \text{liczba}
n, !3.6 million(7 cyfr)\text{3.6 million} \\\\ \text{(7 cyfr)}65-cyfrowaliczba\text{65-cyfrowa} \\\\ {\text{liczba}}161-cyfrowaliczba\text{161-cyfrowa} \\\\ {\text{liczba}}623-cyfrowaliczba\text{623-cyfrowa} \\\\ {\text{liczba}}niewyobraz˙alnieduz˙a 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ń!

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.