Wyjaśnienie złożoności czasowej i przestrzennej algorytmu
Wyobraź sobie dwa programy, które wykonują dokładnie to samo zadanie. Podaj każdemu z nich tysiąc rekordów i nie będziesz w stanie ich rozróżnić. Podaj im jednak miliard, a jeden skończy, zanim puścisz klawisz Enter, podczas gdy drugi będzie nadal pracował w następny wtorek.
Ten sam laptop. Te same dane. To, co je dzieli, to złożoność czasowa, czyli po prostu nazwa określająca, jak szybko obciążenie algorytmu rośnie wraz z ilością danych wejściowych.
Omówimy, co właściwie oznacza ten termin, jak zapisuje się go w notacji Wielkiego O, jak wywnioskować go z prawdziwego fragmentu kodu i gdzie pojawia się złożoność przestrzenna. Następnie, na końcu, przejdziemy do miejsca, w którym to wszystko przestaje być pracą domową, a zaczyna kosztować realne pieniądze: inteligentnych kontraktów.
Czym jest złożoność czasowa algorytmu?
Zapomnij na chwilę o sekundach. Złożoność czasowa liczy kroki. Porównania, zadania, trochę arytmetyki tu i tam, a sumę zapisujesz jako funkcję n, czyli rozmiaru danych wejściowych.
Oto najnudniejsza funkcja, jaką można sobie wyobrazić:
python def print_all(items): dla elementu w elementach: print(item)
Dziesięć przedmiotów? Dziesięć przejść przez pętlę. Dziesięć tysięcy? Dziesięć tysięcy przejść.
Praca porusza się w linii prostej wzdłuż wejścia, dlatego nazywamy to O(n).
No cóż, może każda podróż rzeczywiście kosztuje trzy małe operacje zamiast jednej. Dobra, to 3n. Szczerze mówiąc, nikogo to nie obchodzi, bo podwojenie listy i tak podwaja pracę, a ta krzywa wzrostu to właśnie to, czego nam potrzeba. Dokładna liczba jest celowo pomijana.
Dlatego też każdy kurs DSA i połowa rozmów kwalifikacyjnych z kodowaniem kładzie nacisk na złożoność czasową. Jeśli potrafisz odczytać złożoność algorytmu, patrząc na niego, możesz odgadnąć, jak zachowa się na danych wejściowych, których nigdy nie testowałeś. A w środowisku produkcyjnym stanowią one większość danych.
Dlaczego czas wykonania jest słabą miarą algorytmu
Dlaczego więc po prostu nie uruchomić tego z timerem? Wiele osób tak robi i rozumiem to. Problem w tym, że czas wykonania wciąga masę rzeczy, z którymi twój algorytm nie ma nic wspólnego:
- Sprzęt. Mój pięcioletni laptop i nowiutki cloud box dadzą ci zupełnie różne wyniki dla tego samego skryptu.
- Język programowania. Napisz tę samą pętlę w C i Pythonie, a zobaczysz przerwę 10-krotną, a nawet większą.
- Obciążenie systemu. Uruchomił się jakiś aktualizator w tle, wybudził się moduł zbierający śmieci, pamięć podręczna jest zimna. Twój wynik się zmienia.
- Niezależnie od tego, jakie dane wejściowe udało Ci się zebrać. Sortowanie, które działa na prawie posortowanych danych, może działać również na potasowanych danych.
Stoper daje ci jeden pomiar na jednym polu z jednym wejściem. Zapytaj go o dane 100 razy większe, a nic nie znajdzie.
Liczba kroków nie jest chwiejna. Ten sam algorytm, te same dane wejściowe i otrzymujesz tę samą liczbę kroków, niezależnie od tego, czy to Rust na serwerze rack, czy JavaScript na czyimś telefonie. Dlatego złożoność czasowa to uczciwa walka między dwoma rozwiązaniami, zanim cokolwiek przetestujesz. Ja i tak bym to później porównał, jeśli to coś znaczy. To po prostu inna kwestia.
Wyjaśnienie Big O i innych notacji asymptotycznych
W podręcznikach nazywa się to notacją asymptotyczną, co brzmi gorzej niż jest w rzeczywistości. Pozwalasz, by n stało się ogromne i przestajesz przejmować się drobiazgami, więc stałe mnożniki i niewielkie nakłady wypadają, a przetrwa tylko krzywa wzrostu. Warto znać trzy z nich:
| Notacja | Co to opisuje | Zwykłe znaczenie | Przykład |
|---|---|---|---|
| Duże O, O(f(n)) | Górna granica | Algorytm nie rośnie szybciej niż f(n) | Przeszukiwanie liniowe ma czas O(n) |
| Duża Omega, Ω(f(n)) | Dolna granica | Algorytm wymaga co najmniej pracy f(n) | Każde sortowanie porównawcze jest Ω(n log n) |
| Duża Theta, Θ(f(n)) | Ścisłe wiązanie | Górna i dolna granica są zgodne | Sortowanie przez scalanie to Θ(n log n) |
W praktyce notację Big O usłyszysz w około 95% przypadków. Ustawia ona górną granicę, co oznacza, że czas wykonania nie będzie rósł szybciej niż tempo podane w nawiasach. Podczas mojej pierwszej recenzji kodu w prawdziwej pracy starszy programista napisał „O(n²), proszę poprawić” obok zagnieżdżonej pętli, co oznaczało, że złożoność czasowa w najgorszym przypadku była kwadratowa, a lista miała się znacznie wydłużyć.
Omega i Theta głównie uczęszczają na zajęcia uniwersyteckie z analizy algorytmów i chyba od lat nie pisałem żadnego z nich w pracy. Big O wygrywa, ponieważ odpowiada na pytanie, o które ludzie pytają na spotkaniu, czyli: „Jak źle się to skończy, jeśli ruch się potroi?”.
Jest jeden szczegół techniczny, który przez jakiś czas mnie zastanawiał. Ponieważ Big O to tylko sufit, funkcja O(n) jest również O(n²), ściśle rzecz biorąc, tak samo jak osoba o wzroście 1,5 metra ma „poniżej 2 metrów”. Prawda i bezużyteczna. Każdy podaje najwęższą granicę, jaką potrafi uzasadnić, i ja zrobię to samo.
Typowe klasy złożoności czasowej z przykładami
W prawdziwym kodzie nie ma zbyt wielu klas, może siedem, jeśli liczyć te przerażające. Oto mniej więcej, ile kosztuje każda z nich przy n = 1000:
| Klasa | Nazwa | Typowy przykład | Operacje przy n = 1000 |
|---|---|---|---|
| O(1) | Stały | Indeks tablicy, wyszukiwanie w tablicy skrótów | 1 |
| O(log n) | Logarytmiczny | Wyszukiwanie binarne | ~10 |
| NA) | Liniowy | Skanowanie listy | 1000 |
| O(n log n) | Liniowy | Sortowanie przez scalanie, sortowanie szybkie (średnie) | ~10 000 |
| O(n²) | Kwadratowy | Pętle zagnieżdżone, sortowanie bąbelkowe | 1 000 000 |
| O(2ⁿ) | Wykładniczy | Naiwny rekurencyjny Fibonacci | Więcej niż atomy we wszechświecie |
| NA!) | Silnia | Sprzedawca podróżujący z użyciem siły | Jeszcze większy |
O(1): Stały czas
Niezależnie od tego, czy Twój słownik Pythona ma dziesięć, czy dziesięć milionów kluczy, wyciągnięcie jednego po kluczu kosztuje mniej więcej tyle samo, podobnie jak odczytanie elementów[5] z listy. Ta płaskość stanowi istotę stałego czasu.
O(log n): Czas logarytmiczny
Myślę o nich jak o algorytmach typu „zgadnij liczbę od 1 do 100”, gdzie każde odgadnięcie wyklucza połowę tego, co pozostało. Wyszukiwanie binarne działa dokładnie tak samo na posortowanej liście:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 jeśli arr[mid] == cel: zwróć mid jeśli arr[mid] < cel: lo = mid + 1 w przeciwnym razie: hi = mid - 1 zwróć -1
Przy miliardzie posortowanych elementów potrzeba około 30 porównań, natomiast przeglądanie ich jeden po drugim może zająć cały miliard. I nigdy nie przestało mnie to śmieszyć.
O(n) i O(n log n)
Algorytm liniowy odwiedza każdy element ustaloną liczbę razy, tak jakbyś szukał na oko największej liczby w kolumnie arkusza kalkulacyjnego. O(n log n) to podstawa porządnego sortowania. Sortowanie przez scalanie dzieli listę na pojedyncze elementy (log n poziomów podziału), a następnie wykonuje jedno przejście liniowe na każdym poziomie podczas scalania, dzięki czemu czas działania pozostaje taki sam, niezależnie od tego, czy dane docierają posortowane, czy pomieszane.
O(n²) i gorzej
Kod kwadratowy prawie zawsze ma pętlę ukrytą w innej pętli, jak ta kontrola duplikatów, która porównuje każdą parę:
python def has_duplicate(elementy): dla i w zakresie(len(elementy)): dla j w zakresie(i + 1, len(elementy)): jeśli elementy[i] == elementy[j]: zwróć wartość True zwróć wartość False
Wzrost wykładniczy i czynnikowy są o niebo gorsze. Podręcznikowy rekurencyjny ciąg Fibonacciego ciągle rozwiązuje te same podproblemy, więc każde +1 przy n mniej więcej podwaja pracę. Przy n = 20 nie zauważysz tego; przy n = 60 możesz ugotować obiad, zjeść go, pozmywać, a i tak nie będzie gotowy.
Jak obliczyć złożoność czasową krok po kroku
Prawie nigdy nie potrzebujesz formalnego dowodu, aby obliczyć złożoność czasową. Przerabiam w myślach tę listę i pokrywa ona większość kodu, jaki widzę:
- Zdefiniuj n. Określ, jaki jest rozmiar danych wejściowych: długość listy, liczba węzłów w grafie, liczba cyfr w liczbie.
- Policz pracę w każdym wierszu. Proste instrukcje (przypisania, porównania, arytmetyka) kosztują O(1).
- Dodaj bloki sekwencyjne. Dwie pętle jedna po drugiej, każda po n, dają n + n = 2n.
- Mnożenie zagnieżdżonych bloków. Pętla po n wewnątrz innej pętli po n daje n × n = n².
- Usuń stałe. 2n zmienia się w n, a 500 zmienia się w 1.
- Zachowaj tylko wyraz dominujący. W n² + n, część n² przyćmiewa resztę w miarę wzrostu n.
Szybko, policzyłem. Wynik to T(n) = 3n² + 5n + 2. Wprowadź milion: 3n² to trzy biliony, 5n to pięć milionów. Błąd zaokrąglenia. Powiedzmy, że to O(n²), gotowe.
Pętle, które pomijają elementy zamiast przechodzić obok nich, są bardziej podstępne:
python def count_halvings(n): kroki = 0, podczas gdy n > 1: n //= 2 kroki += 1 return steps
Każde przejście zmniejsza n o połowę, więc ta pętla while poddaje się po około log₂(n) rundach. Co w zasadzie stanowi pełną odpowiedź na pytanie „kiedy złożoność czasowa wynosi O(log n)?”. Jeśli to, co pozostaje, zmniejsza się o stały współczynnik w każdym kroku, to jesteś u celu.
Rekurencja potrzebuje jeszcze jednego narzędzia – rekurencji. Sortowanie przez scalanie wykonuje dwa zadania o połowę mniejsze, a następnie scalanie, więc T(n) = 2T(n/2) + n. Twierdzenie główne to ściągawka dotycząca rekurencji tego typu, a w tym przypadku zwraca O(n log n).
I praktyczna zasada z programowania konkursowego, na której często się opieram: normalna maszyna wykonuje około 10⁸ prostych operacji na sekundę. Bardzo to uproszczone, ale wystarcza do sprawdzenia złożoności czasowej rozwiązania przed kliknięciem „Wyślij”. Przy n równym 10⁵, O(n²) wynosi około 10¹⁰ operacji, więc limit czasu zostaje przekroczony. O(n log n) wynosi poniżej 2 milionów. Przechodzi gładko.
Analiza najgorszego, najlepszego i przeciętnego przypadku
Wprowadź do tego samego algorytmu różne dane wejściowe, a ilość pracy może gwałtownie wzrosnąć. Przeszukiwanie liniowe dobrze to pokazuje:
- W najlepszym przypadku: chcesz być na samym czele. Jedno porównanie i odpadasz.
- W najgorszym przypadku jest na samym końcu albo w ogóle go nie ma. To tyle porównań.
- Przeciętny przypadek: jeśli istnieje jakiekolwiek prawdopodobieństwo, że będzie to gdziekolwiek, sprawdzisz średnio około n/2. Nadal O(n), pamiętaj.
Zapytaj programistę o „złożoność” czegoś, a prawie zawsze poda ci najgorszy możliwy scenariusz złożoności czasowej, ponieważ ta liczba to obietnica, którą można uwzględnić w planach.
Załóżmy, że Twoje API obsługuje żądanie w najgorszym przypadku z szybkością O(n). Świetnie, teraz wiesz, jak zachowuje się najwolniejsze żądanie, a dodatkowo jesteś zabezpieczony, gdy ktoś celowo wysyła Ci śmieci. Ludzie po prostu tak robią: jeśli atakujący odkryje, które klucze powodują kolizję w Twojej tablicy skrótów, to przez jakiś czas będą widoczne tylko te klucze.
Warto przyjrzeć się przeciętnemu przypadkowi, gdy zły scenariusz rzadko się zdarza. Quicksort jest tu sztandarowym przykładem, uśredniając O(n log n), ale spadając do O(n²), jeśli naiwnie wybierzesz pivoty na danych, które są już posortowane. Biblioteki standardowe radzą sobie z tym, używając losowych pivotów lub przełączając się na inny algorytm sortowania, gdy rekursja osiągnie podejrzanie dużą głębokość.
Czym jest złożoność przestrzenna i przestrzeń pomocnicza?
Pamięć to kolejny rachunek, jaki generuje algorytm. Złożoność pamięci śledzi, ile jej potrzebujesz w miarę wzrostu rozmiaru danych wejściowych, i zapisuje się ją tą samą notacją Wielkiego O, co czas.
Część tej pamięci to samo wejście, za które płacisz niezależnie od tego, co z nim zrobisz. Część, którą faktycznie kontrolujesz, nazywa się przestrzenią pomocniczą, czyli dodatkowymi elementami przydzielanymi przez kod podczas działania, takimi jak zmienne tymczasowe i nowe tablice, a także stos wywołań, o którym nikt nie pamięta, dopóki go nie ugryzie.
Kilka szybkich przypadków:
- Zamiana dwóch zmiennych wymaga niezależnie od wszystkiego kilku slotów, więc jest to przestrzeń pomocnicza O(1).
- Skopiowanie listy n elementów do nowej listy kosztuje Cię O(n) dodatkowej pamięci.
- Rekursja na poziomie n powoduje, że n ramek pozostaje na stosie, co stanowi przestrzeń O(n), nawet jeśli nigdy nie zbudowałeś tablicy.
Widziałem, jak początkujący programista stracił całe popołudnie na to ostatnie. Jego funkcja rekurencyjna wyglądała, jakby w ogóle nie używała pamięci, ale każde niedokończone wywołanie było zaparkowane na stosie, czekając na powrót tych z głębszych warstw, a przy dużym wejściu cały system umierał z powodu przepełnienia stosu.
Wiele optymalizacji polega po prostu na wymianie pamięci na czas lub odwrotnie. Memoizacja buforuje już obliczone wyniki, co skraca czas Fibonacciego z O(2ⁿ) do O(n) w zamian za O(n) pamięci. Tabele skrótów zapewniają średnią liczbę wyszukiwań O(1) poprzez poświęcenie miejsca na kontenery. Na serwerze z 64 GB pamięci RAM taka wymiana jest zazwyczaj oczywista, ale na mikrokontrolerze lub w inteligentnym kontrakcie warto się dwa razy zastanowić.
Złożoność czasowa i przestrzenna typowych struktur danych
Wybór odpowiedniej struktury danych zazwyczaj jest lepszy niż mikrodostrajanie tego, co znajduje się w pętli. Średnie koszty dla tych, po które najczęściej sięgasz:
| Struktura danych | Dostęp | Szukaj | Wstawić | Usuwać | Przestrzeń |
|---|---|---|---|---|---|
| Szyk | O(1) | NA) | NA) | NA) | NA) |
| Lista powiązana | NA) | NA) | O(1) | O(1) | NA) |
| Tablica mieszająca | brak danych | O(1) | O(1) | O(1) | NA) |
| Zrównoważone drzewo poszukiwań binarnych | O(log n) | O(log n) | O(log n) | O(log n) | NA) |
| Stos binarny | O(1) dla min/maks | NA) | O(log n) | O(log n) | NA) |
Dwa przypisy. Wstawianie i usuwanie na liście powiązanej ma złożoność O(1), jeśli masz już węzeł. Tablica skrótów może spaść do O(n), gdy wiele kluczy koliduje.
Algorytmy sortowania różnią się równie mocno:
| Algorytm sortowania | To, co najlepsze | Przeciętny | Najgorszy | Przestrzeń pomocnicza |
|---|---|---|---|---|
| Sortowanie bąbelkowe | NA) | O(n²) | O(n²) | O(1) |
| Sortowanie przez scalanie | O(n log n) | O(n log n) | O(n log n) | NA) |
| Szybkie sortowanie | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Sortowanie kopcowe | O(n log n) | O(n log n) | O(n log n) | O(1) |
Sortowanie przez scalanie jest przewidywalne, ale wymaga dodatkowej pamięci. Sortowanie przez kopcowanie sortuje w miejscu i zachowuje ten sam najgorszy przypadek. Szybkie sortowanie, pomimo gorszego sufitu, w praktyce zazwyczaj wygrywa.
Złożoność czasowa w blockchainie i inteligentnych kontraktach
I tu zaczyna się zabawa. Na Twoim własnym serwerze niechlujny algorytm marnuje procesor i może denerwować użytkownika. W Ethereum lub dowolnym łańcuchu EVM marnuje pieniądze. Każdy kod operacji wykonywany przez inteligentny kontrakt kosztuje gaz, opłacany w natywnej walucie łańcucha, więc liczba operacji pojawia się jako pozycja na czyimś rachunku. Innymi słowy, zła złożoność czasowa ma swoją cenę.
Załóżmy, że masz kontrakt, który obejmuje każdego posiadacza tokena, aby wypłacić nagrody. O(n), a gaz rośnie z każdym nowym posiadaczem. W dniu premiery nikt tego nie zauważa.
Potem lista posiadaczy ciągle rośnie. Pewnego dnia wypłata wymaga więcej gazu niż limit gazu blokowego, który jest limitem ilości gazu mieszczącego się w jednym bloku. Potem transakcja nie może zostać zrealizowana. Nie chodzi o „to jest powolne”. Po prostu nigdy się nie udaje, a środki, które czekały za tą funkcją, w zasadzie utknęły. Audytorzy rejestrują takie nieograniczone pętle w ramach odmowy usługi i jest to w porządku.
Rozwiązania te opierają się na prostym i czystym myśleniu złożonym:
- Podziel pracę na partie o stałym rozmiarze obejmujące kilka transakcji.
- Odwróć to tak, aby każdy użytkownik mógł odebrać własną nagrodę. Każde wywołanie jest O(1).
- Zamień pętlę na dowód Merkle'a.
Uwielbiam dowody Merkle'a jako przykład tego, dlaczego log n ma tak duże znaczenie w łańcuchu. Drzewo Merkle'a haszuje dużą ilość danych w jeden hash główny.
Aby udowodnić, że jeden wpis należy do zbioru n, potrzeba około log₂(n) skrótów. Dla miliona wpisów to około 20. Nie milion. Airdropy opierają się na tym, a lekkie portfele Bitcoin wykorzystują tę samą sztuczkę do potwierdzania transakcji bez pobierania całego bloku.
Poza łańcuchem, to samo. Wyobraź sobie system płatności, który dopasowuje każdą przychodzącą transakcję blockchain do faktury, skanując każdą otwartą. O(n) na płatność, a wraz z rozwojem sklepu staje się to wolniejsze. Umieść faktury na mapie skrótów z kluczem adresu lub identyfikatora, a każde dopasowanie będzie miało współczynnik O(1). A jeśli wolisz nie budować i nie zarządzać tym samodzielnie, bramka płatności kryptowalutowych, taka jak Plisio, zrobi to za Ciebie.
