Stały czas
Mówią, że algorytm to algorytm stały czas(zapisywane jako czas O(1)), jeśli wartość T(N) jest ograniczona do wartości niezależnej od wielkości wejścia. Na przykład pobranie jednego elementu tablicy zajmuje stały czas, ponieważ w celu jego zlokalizowania wykonywane jest pojedyncze polecenie. Jednak znalezienie minimalnej wartości w nieposortowanej tablicy nie jest operacją stałą, ponieważ musimy przejść przez każdy element tablicy. Zatem operacja ta zajmuje czas liniowy O(n). Jeżeli liczba elementów jest znana z góry i się nie zmienia, to taki algorytm można nazwać algorytmem czasu stałego.
Pomimo nazwy „czas stały”, czas działania nie musi być niezależny od wielkości problemu, ale górna granica czasu działania nie powinna. Na przykład zadanie „wymień wartości A I B, jeśli to konieczne, aby wynik był A≤B", jest uważany za problem stałego czasu, chociaż czas działania algorytmu może zależeć od tego, czy nierówność już zachodzi A ≤ B albo nie. Istnieje jednak pewna stała T, dla którego czas wykonania zadania jest zawsze nie przekracza T.
Poniżej znajduje się kilka przykładów kodu działającego w czasie stałym:
Indeks całkowity = 5; int element = lista; Jeśli(warunek jest prawdziwy) Następniew przeciwnym razie wykonywać pewne operacje ze stałym czasem działania Do ja = 1 Do 100 Do j = 1 Do 200 wykonuje pewne operacje ze stałym czasem działania
Jeśli T(N) jest równe O( jakąś stałą wartość), jest to równoważne T(N) to O(1).
Czas logarytmiczny
czas logarytmiczny, Jeśli T(N) = O(log N) . Ponieważ komputery używają binarnego systemu liczbowego, 2 jest podstawą logarytmu (tj. log 2 N). Jednak kiedy wymiana podstawy logarytmy log a N i zaloguj b N różnią się jedynie stałym czynnikiem, który jest odrzucany w zapisie O-big. Zatem O (log N) to standardowy zapis algorytmów czasu logarytmicznego, niezależnie od podstawy logarytmu.
Algorytmy działające w czasie logarytmicznym są powszechnie spotykane podczas wykonywania operacji na drzewach binarnych lub podczas korzystania z wyszukiwania binarnego.
Algorytmy O(log n) są uważane za wysoce wydajne, ponieważ czas operacji na element maleje wraz ze wzrostem liczby elementów.
Bardzo prostym przykładem takiego algorytmu jest dzielenie ciągu na pół, druga połowa jest ponownie dzielona na pół i tak dalej. Zajmuje to czas O(log n) (gdzie n jest długością łańcucha, zakładamy, że konsola.log I str.podciąg zająć stały czas). Oznacza to, że aby zwiększyć liczbę wydruków, należy podwoić długość linii.
// Funkcja rekursywnie drukująca prawą połowę linii var prawo = funkcja (str) (var długość = długość str.; // funkcja pomocnicza var pomoc = funkcja (indeks) ( // Rekurencja: wydrukuj prawą połowę jeśli (indeks< length ) { // Wypisuje znaki od indeksu do końca linii konsola. log(str. podciąg(indeks, długość)); // wywołanie rekurencyjne: wywołanie funkcji pomocniczej prawą stroną pomoc (Math . ceil ((długość + indeks ) / 2 )); ) ) pomoc ( 0 ); )
Czas polilogu
Mówi się, że algorytm się uruchamia czas polilogu, Jeśli T(N) = O((log N) k), dla niektórych k. Na przykład problem rzędu mnożenia macierzy można rozwiązać w czasie polilogarytmicznym według równoległa maszyna RAM .
Czas subliniowy
Mówi się, że algorytm się uruchamia czas subliniowy, Jeśli T(N) = o( N). W szczególności dotyczy to algorytmów złożoności czasowej wymienionych powyżej, a także innych, takich jak wyszukiwanie Grovera ze złożonością O( N ½).
Typowe algorytmy, które choć dokładne, to jednak działają w czasie subliniowym, wykorzystują równoległość procesów (jak ma to miejsce w przypadku algorytmu NC 1 do obliczania wyznacznika macierzy), obliczenia nieklasyczne (jak w przypadku poszukiwania Grovera) lub mają gwarantowane założenie o strukturę danych wejściowych (jak te działające w czasie logarytmicznym, algorytmy wyszukiwania binarnego i wiele algorytmów przetwarzania drzew). Jednakże konstrukcje formalne, takie jak zbiór wszystkich ciągów znaków mających bit 1 w pozycji określonej przez pierwsze log(n) bity ciągu, mogą zależeć od każdego bitu sygnału wejściowego, ale nadal być podliniowe w czasie.
Termin algorytm z subliniowym czasem działania zwykle używane w przypadku algorytmów, które w przeciwieństwie do powyższych przykładów działają na zwykłych modelach maszyn sekwencyjnych i nie zakładają a priori wiedzy o strukturze wejściowej. Dopuszczalne jest jednak dla nich stosowanie metod probabilistycznych, a co więcej, w przypadku większości trywialnych problemów algorytmy muszą być probabilistyczne.
Ponieważ taki algorytm musi generować odpowiedź bez pełnego odczytania danych wejściowych, jest to w dużym stopniu zależne od metod dostępu dozwolonych w strumieniu wejściowym. Zwykle dla strumienia, który jest ciągiem bitowym B 1 ,...,b k zakłada się, że algorytm może zażądać wartości w czasie O(1). b ja dla kazdego I.
Algorytmy czasu podliniowego są zwykle probabilistyczne i zapewniają jedynie przybliżone rozwiązanie. Subliniowe algorytmy czasu wykonania pojawiają się naturalnie podczas badań kontrole nieruchomości.
Czas liniowy
czas liniowy, Lub O( N) , jeśli jego złożoność wynosi O( N). Nieformalnie oznacza to, że wystarczy duży rozmiar danych wejściowych, czas działania rośnie liniowo wraz z rozmiarem danych wejściowych. Na przykład procedura sumująca wszystkie elementy listy wymaga czasu proporcjonalnego do długości listy. Opis ten nie jest do końca dokładny, gdyż czas działania może znacząco odbiegać od dokładnej proporcjonalności, szczególnie w przypadku małych wartości N.
Czas liniowy jest często postrzegany jako pożądana cecha algorytmu. Przeprowadzono wiele badań w celu stworzenia algorytmów o (prawie) liniowym czasie działania lub lepszym. Badania te obejmowały zarówno podejście programowe, jak i sprzętowe. W przypadku wykonania sprzętowego niektóre algorytmy, które z matematycznego punktu widzenia nigdy nie mogą osiągnąć liniowego czasu wykonania w standardowych modelach obliczeniowych, mogą działać w czasie liniowym. Istnieją pewne technologie sprzętowe, które wykorzystują równoległość, aby osiągnąć ten cel. Przykładem jest pamięć skojarzeniowa. Ta koncepcja czasu liniowego jest używana w algorytmach porównywania ciągów, takich jak algorytm Boyera-Moore'a i algorytm Ukkonena.
Czas quasilinearny
Mówi się, że algorytm działa w czasie quasi-liniowym, jeśli T(N) = O( N dziennik k N) dla jakiejś stałej k. Czas liniowo-logarytmiczny jest przypadkiem szczególnym k= 1 . Używając notacji słabego O, algorytmy te to Õ( N). Algorytmy czasu quasilinearnego są również o( N 1+ε) dla dowolnego ε > 0 i działają szybciej niż jakikolwiek wielomian w N
Algorytmy działające w czasie quasi-liniowym, oprócz wspomnianych powyżej algorytmów liniowo-logarytmicznych, obejmują:
- Sortowanie przez scalanie w miejscu, O( N dziennik 2 N)
- Szybkie sortowanie, O( N dziennik N), w wersji probabilistycznej ma liniowo-logarytmiczny czas wykonania w najgorszym przypadku. Wersja nieprobabilistyczna ma liniowo-logarytmiczny czas wykonania tylko w celu średniego pomiaru złożoności.
- Heapsort, O( N dziennik N), sortowanie przez scalanie, sortowanie introsortacyjne, sortowanie według drzewa binarnego, sortowanie gładkie, sortowanie pasjansa itp. w najgorszym
- Szybkie transformacje Fouriera, O( N dziennik N)
- Obliczanie macierzy Monge'a, O( N dziennik N)
Czas liniowo-logarytmiczny
Liniowo-logarytmiczny jest szczególnym przypadkiem czasu quasi-liniowego z wykładnikiem k= 1 w wyrażeniu logarytmicznym.
Funkcja liniowo-logarytmiczna jest funkcją formy N dziennik N(tj. praca liniowy i logarytmiczne). Mówią, że algorytm działa czas liniowo-logarytmiczny, Jeśli T(N) = O( N dziennik N) . Zatem wyraz liniowo-logarytmiczny rośnie szybciej niż składnik liniowy, ale wolniej niż jakikolwiek wielomian N ze stopniem wyraźnie większym niż 1.
W wielu przypadkach czas działania N dziennik N jest po prostu wynikiem wykonania operacji Θ(log N) N raz. Na przykład sortowanie drzewa binarnego tworzy drzewo binarne, wstawiając każdy element do tablicy o rozmiarze n jeden po drugim. Od operacji wstawiania do zrównoważone drzewo wyszukiwania binarnego zajmuje czas O(log). N), całkowity czas wykonania algorytmu będzie liniowo-logarytmiczny.
Sortowanie porównawcze wymagają co najmniej liniowo-logarytmicznej liczby porównań dla najgorszego przypadku, ponieważ log( N!) = Θ( N dziennik N) zgodnie ze wzorem Stirlinga. Ten sam czas wykonania często wynika z równania powtarzalności T(N) = 2 T(N/2) + O( N).
Czas subkwadratowy
Kilka przykładów wielomianowych algorytmów czasu:
Czas ściśle i słabo wielomianowy
W niektórych kontekstach, szczególnie w optymalizacji, rozróżnia się algorytmy z ścisły czas wielomianowy I czas słabo wielomianowy. Te dwie koncepcje mają zastosowanie tylko do danych wejściowych w postaci liczb całkowitych.
W arytmetycznym modelu obliczeń zdefiniowany jest czas ściśle wielomianowy. W tym modelu podstawowe operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie i porównywanie) są traktowane jako jednostki wykonania, niezależnie od długości operandów. Algorytm działa w czasie ściśle wielomianowym jeśli
- liczba operacji w modelu obliczeń arytmetycznych jest ograniczona wielomianem liczby liczb całkowitych w strumieniu wejściowym, oraz
- Pamięć wykorzystywana przez algorytm jest ograniczona wielomianem wielkości wejściowej.
Dowolny algorytm posiadający te dwie właściwości można zredukować do algorytmu czasu wielomianowego, zastępując operacje arytmetyczne odpowiednimi algorytmami wykonywania operacji arytmetycznych na maszynie Turinga. Jeżeli drugi z powyższych wymogów nie zostanie spełniony, nie będzie to już prawdą. Biorąc pod uwagę liczbę całkowitą (która zajmuje pamięć proporcjonalnie do n w maszynie Turinga), można ją obliczyć za pomocą n operacji, stosując wielokrotne potęgowanie. Jednak pamięć używana do reprezentacji 2 2 n (\ Displaystyle 2 ^ (2 ^ (n))), proporcjonalny 2 n (\ displaystyle 2 ^ (n)) i zależy to wykładniczo, a nie wielomianowo od pamięci używanej na wejściu. Dlatego nie jest możliwe wykonanie tych obliczeń w czasie wielomianowym na maszynie Turinga, ale można je wykonać w wielomianowej liczbie operacji arytmetycznych.
I odwrotnie, istnieją algorytmy, które działają w liczbie kroków maszyny Turinga ograniczonej długością wielomianu zakodowanego binarnie wejścia, ale nie działają w liczbie operacji arytmetycznych ograniczonej wielomianem liczby liczb na wejściu. Jednym z przykładów jest algorytm Euklidesa służący do obliczania największego wspólnego dzielnika dwóch liczb całkowitych. Dla dwóch liczb całkowitych za (\ displaystyle a) I b (\ displaystyle b) Czas działania algorytmu jest ograniczony O ((log za + log b) 2) (\ Displaystyle O ({\ log \ a+ \ log \ b) ^ (2)}) kroki maszyny Turinga. Liczba ta jest wielomianem rozmiaru binarnej reprezentacji liczb za (\ displaystyle a) I b (\ displaystyle b), co można z grubsza przedstawić jako log za + log b (\ displaystyle \ log \ a + \ log \ b). Jednocześnie nie można ograniczyć liczby operacji arytmetycznych do liczby liczb całkowitych na wejściu (która w tym przypadku jest stała - na wejściu są tylko dwie liczby). Z uwagi na tę uwagę algorytm nie działa w czasie ściśle wielomianowym. Czas rzeczywisty działanie algorytmu zależy od wielkości za (\ displaystyle a) I b (\ displaystyle b), a nie tylko liczbę liczb całkowitych na wejściu.
Jeśli algorytm działa w czasie wielomianowym, ale nie w ściśle wielomianowym, mówi się, że działa czas słabo wielomianowy. Dobrze znanym przykładem problemu, dla którego znany jest algorytm słabo wielomianowy, ale nie jest znany algorytm ściśle wielomianowy, jest programowanie liniowe. Słabo czasu wielomianowego nie należy mylić z czasem pseudowielomianowym.
Klasy trudności
Pojęcie czasu wielomianowego prowadzi do kilku klas złożoności w teorii złożoności obliczeniowej. Poniżej podano kilka ważnych klas zdefiniowanych przy użyciu czasu wielomianowego.
- : Klasa problemów rozwiązywalnych w czasie wielomianowym na deterministycznej maszynie Turinga.
- : Klasa złożoności problemów rozwiązywalności, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie wielomianowym.
- ZPP: Klasa złożoności problemów rozwiązywanych, które można rozwiązać z zerowym błędem w probabilistycznej maszynie Turinga w czasie wielomianowym.
- : Klasa złożoności problemów rozwiązywanych, które można rozwiązać za pomocą błędów jednostronnych w probabilistycznej maszynie Turinga w czasie wielomianowym.
- BPP probabilistyczna maszyna Turinga w czasie wielomianowym.
- BQP: Klasa złożoności problemów rozwiązywanych, które można rozwiązać za pomocą błędów dwukierunkowych w kwantowej maszynie Turinga w czasie wielomianowym.
P jest najmniejszą klasą złożoności czasowej na maszynie deterministycznej, tj zrównoważony w zakresie zmiany modelu samochodu. (Na przykład przejście z jednotaśmowej maszyny Turinga na wielotaśmową maszynę Turinga może skutkować kwadratowym przyspieszeniem, ale każdy algorytm działający w czasie wielomianowym w jednym modelu będzie działał w czasie wielomianowym w drugim.)
Czas superwielomianowy
Mówią, że algorytm działa czas superwielomianowy, Jeśli T(N) nie jest ograniczony powyżej wielomianem. Czas ten jest równy ω( N C) dla wszystkich stałych C, Gdzie N- parametr wejściowy, zwykle liczba bitów wejściowych.
Na przykład algorytm, który implementuje 2 N kroki, aby wprowadzić rozmiar N wymaga czasu superwielomianowego (dokładniej czasu wykładniczego).
Oczywiście algorytm wykorzystujący zasoby wykładnicze jest superwielomianem, ale niektóre algorytmy są bardzo słabo superwielomianem. Na przykład, Test prostoty Adlemana-Pomeranza-Roumeliego* działa na czas N O(log log N) NA N-bitowe wejście. To rośnie szybciej niż jakikolwiek wielomian dla wystarczająco dużego N, ale rozmiar danych wejściowych musi stać się bardzo duży, aby nie został zdominowany przez wielomian niskiego stopnia.
Algorytm wymagający czasu superwielomianowego leży poza klasą złożoności. Teza Cobhama twierdzi, że algorytmy te są niepraktyczne i w wielu przypadkach rzeczywiście tak jest. Ponieważ problem równości klas P i NP nie został rozwiązany, nie są obecnie znane żadne algorytmy rozwiązywania problemów NP-zupełnych w czasie wielomianowym.
Czas quasiwielomianowy
Algorytmy czas quasi-wielomianowy to algorytmy, które działają wolniej niż czas wielomianowy, ale nie tak wolno jak algorytmy czasu wykładniczego. W najgorszym przypadku czas działania algorytmu quasi-wielomianowego wynosi C. Dobrze znany klasyczny algorytm rozkładu na czynniki liczby całkowitej, , Nie jest quasi-wielomianem, ponieważ czasu działania nie można przedstawić jako 2 O ((log n) do) (\ Displaystyle 2 ^ (O ((\ log n) ^ (c)))) dla niektórych stałe C. Jeśli stała „c” w definicji quasi-wielomianowego algorytmu czasu wynosi 1, otrzymamy algorytm czasu wielomianowego, a jeśli jest mniejsza niż 1, otrzymamy algorytm czasu podliniowego.
Algorytmy czasu quasi-wielomianowego zwykle powstają, gdy redukuje się problem NP-trudny do innego problemu. Na przykład możesz wziąć problem NP-trudny, powiedzmy 3SAT, i zredukować go do innego problemu B, ale rozmiar problemu będzie 2 O ((log n) do) (\ Displaystyle 2 ^ (O ((\ log n) ^ (c)))). W tym przypadku redukcja nie dowodzi, że problem B jest NP-trudny, pokazuje jedynie, że nie ma algorytmu wielomianowego dla B, chyba że istnieje algorytm quasi-wielomianowy dla 3SAT (i wtedy dla wszystkich -problemów). Podobnie istnieją pewne problemy, dla których znamy algorytmy czasu quasi-wielomianowego, ale dla których nie znamy algorytmów czasu wielomianowego. Problemy takie pojawiają się w algorytmach aproksymacyjnych. Znanym przykładem jest zorientowany problem Steinera, dla którego istnieje aproksymacyjny algorytm quasi-wielomianowy ze współczynnikiem aproksymacji O (log 3 n) (\ Displaystyle O (\ log ^ (3) n))(gdzie n jest liczbą wierzchołków), ale istnienie algorytmu czasu wielomianowego jest problemem otwartym.
Klasa trudności Pytanie składa się ze wszystkich problemów, które mają algorytmy czasu quasi-wielomianowego. Można go zdefiniować w kategoriach DTIME w następujący sposób
QP = ⋃ do ∈ N DTIME (2 (log n) c) (\ Displaystyle (\ mbox (QP)) = \ bigcup _ (c \ in \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\log n)^(c))))Powiązanie z problemami NP-zupełnymi
W teorii złożoności nierozwiązany problem równości klas P i NP zadaje pytanie, czy wszystkie problemy w klasie NP mają algorytmy rozwiązywania w czasie wielomianowym. Wszystkie dobrze znane algorytmy problemów NP-zupełnych, takie jak 3SAT, mają czas wykładniczy. Ponadto istnieje hipoteza, że dla wielu naturalnych problemów NP-zupełnych nie ma algorytmów o czasie działania subwykładniczym. Tutaj „czas podwykładniczy” jest rozumiany w znaczeniu drugiej definicji podanej poniżej. (Z drugiej strony wiele problemów teorii grafów, naturalnie reprezentowanych przez macierze sąsiedztwa, można rozwiązać w czasie subwykładniczym po prostu dlatego, że wielkość danych wejściowych jest równa kwadratowi liczby wierzchołków.) To przypuszczenie (dla k- Problem SAT) jest znany jako hipoteza czasu wykładniczego. Ponieważ zakłada się, że problemy NP-zupełne nie mają algorytmów czasu quasi-wielomianowego, pewne wyniki niedokładności w dziedzinie algorytmów aproksymacyjnych zakładają, że problemy NP-zupełne nie mają algorytmów czasu quasi-wielomianowego. Na przykład zobacz dobrze znane wyniki dotyczące nieprzybliżenia problemu pokrycia zbioru.
Czas podwykładniczy
Termin podwykładniczy czas służy do wyrażenia, że czas wykonania jakiegoś algorytmu może rosnąć szybciej niż jakikolwiek wielomian, ale pozostaje znacznie mniejszy niż wykładniczy. W tym sensie problemy, które mają algorytmy z czasem wykładniczym, są łatwiejsze do rozwiązania niż algorytmy z czasem wykładniczym. Dokładna definicja „podwykładniczego” nie jest jeszcze powszechnie przyjęta, dlatego poniżej przedstawiamy dwie najczęstsze definicje.
Pierwsza definicja
Mówi się, że problem jest rozwiązany w czasie podwykładniczym, jeśli jest rozwiązany za pomocą algorytmu, którego logarytm czasu wykonania rośnie mniej niż dowolny dany wielomian. Dokładniej, problem ma czas podwykładniczy, jeśli dla dowolnego ε > 0 istnieje algorytm rozwiązujący problem w czasie O(2 n ε). Zbiór wszystkich takich problemów stanowi klasę złożoności PODEXP, które w kategoriach DTIME można wyrazić jako .
SUBEXP = ⋂ ε > 0 DTIME (2 n ε) (\ Displaystyle (\ tekst (SUBEXP)) = \ bigcap _ (\ varepsilon > 0) (\ tekst (DTIME)) \ lewo (2 ^ (n ^ (\ varepsilon ))\Prawidłowy))Należy zauważyć, że tutaj ε nie jest częścią danych wejściowych i dla każdego ε może istnieć własny algorytm rozwiązania problemu.
Druga definicja
Niektórzy autorzy definiują czas subwykładniczy jako czas działania wynoszący 2 o( N) . Ta definicja pozwala na dłuższe czasy działania niż pierwsza definicja. Przykładem takiego algorytmu czasu podwykładniczego jest dobrze znany klasyczny algorytm rozkładu na czynniki liczb całkowitych, ogólna metoda przesiewania pól liczbowych, która działa w ciągu około 2 O ~ (n 1/3) (\ Displaystyle 2 ^ ({\ tylda (O)) (n ^ (1/3)))), gdzie długość wejściowa wynosi N. Innym przykładem jest dobrze znany algorytm Problemy z izomorfizmem grafów, którego czas działania jest równy 2 O ((n log n)) (\ Displaystyle 2 ^ (O ({\ sqrt (()) n \ log n}}}.
Należy zauważyć, że ma znaczenie, czy algorytm jest podwykładniczy pod względem liczby wierzchołków, czy liczby krawędzi. W sparametryzowana złożoność różnicę tę uwydatnia się poprzez określenie pary, problemu rozwiązywalności i parametru k. PODLEGAĆ jest klasą wszystkich sparametryzowanych zadań wykonywanych w czasie subwykładniczym k i dla wielomianu w N :
SUBEPT = DCZAS (2 o (k) ⋅ poli (n)) . (\ Displaystyle (\ tekst (SUBEPT)) = (\ tekst (DTIME)) \ lewo (2 ^ (o (k)) \ cdot (\ tekst (poly)) (n) \ prawo).)Dokładniej, SUBEPT jest klasą wszystkich sparametryzowanych zadań (L, k) (\ Displaystyle (L, k)), dla którego istnieje funkcja obliczeniowa fa: N → N (\ Displaystyle f: \ mathbb (N) \ do \ mathbb (N) ) Z fa ∈ o (k) (\ Displaystyle f \ w o (k)) i algorytm, który rozwiązuje L podczas 2 fa (k) ⋅ poli (n) (\ Displaystyle 2 ^ (f (k)) \ cdot (\ tekst (poli)) (n)).
Do oceny skuteczności algorytmu najważniejszymi wskaźnikami są:
Czas wykonania algorytmu,
- wymagana ilość pamięci RAM.
W dzisiejszych czasach, ze względu na pół wieku postępu technologicznego, pierwszy wskaźnik (czas realizacji) jest często znacznie ważniejszy niż drugi, dlatego dalej zajmiemy się nim tylko szczegółowo.
Uproszczenia w szacowaniu czasu wykonania algorytmów
W pracach D. Knutha zaproponowano następujące podejście do analizy czasu wykonania algorytmów: na czas całkowity składają się wartości kosztu*częstotliwości dla każdej podstawowej operacji. Podstawowe operacje mogą obejmować dodawanie, mnożenie, dzielenie, pobieranie elementu według indeksu z tablicy, porównywanie liczb całkowitych itp. Łatwo zauważyć, że w tym przypadku obliczenie oszacowania czasu wykonania algorytmu jest dość żmudne. Dlatego A. Turing stwierdził, że wygodnie jest stosować nawet zgrubne przybliżenia szacunków czasu wykonania algorytmów: można przypisywać wagi różnym operacjom w zależności od częstotliwości ich występowania podczas działania algorytmu i uwzględniać tylko te operacje które mają największą wagę. Przykładowo przy mnożeniu macierzy należy brać pod uwagę jedynie takie operacje jak mnożenie i zapisywanie liczb, gdyż To są najczęstsze operacje.Biorąc pod uwagę tylko większośćczęsto powtarzające się operacje - pierwsze uproszczenie, zaproponowany do przybliżonego obliczania czasu wykonania algorytmów.
Drugie uproszczenie polega na odrzuceniu terminów niższego rzędu (tj. terminów), które w niewielkim stopniu przyczyniają się do całkowitego czasu działania algorytmu. Przykładowo (w dalszej części liczba N charakteryzuje wielkość danych wejściowych),
\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),
zamiast \(1/6N^3\) piszą „ten algorytm ma złożoność \(O(N^3)\), zamiast \(3N^4\) piszą „ten algorytm ma złożoność \(O(N ^4)\ )".
Definicja Duże O
Mówi się, że \(f\) jest „O dużym” z \(g\) dla \(x \to x_0\), jeśli istnieje stała \(C>0\) taka, że dla wszystkich \(x\) z otoczenia punktu \(x_0\) zachodzi nierówność \(|f(x)| \leq C|g(x)|\). Poniżej znajduje się ilustracja definicji (oś \(x\) to rozmiar danych wejściowych, oś \(y\) to czas wykonania algorytmu). Widzimy, że począwszy od pewnego punktu, gdy rozmiar danych wejściowych ma tendencję do \(\propto\) \(f(n)\) rośnie wolniej niż \(g(n)\) i ogólnie \(g (n)\) jakby ograniczając to z góry.
Przykłady. \(1 = O(N), N = O(N^2).\)
Wraz z oszacowaniami w postaci \(O(N)\) stosuje się oszacowanie \(\Omega(N)\) (omega duże). Oznacza dolną granicę wzrostu funkcji. Przykładowo, niech liczbę operacji algorytmu opisz funkcją \(f(N)=\Omega(N^2)\). Oznacza to, że nawet w najbardziej udanym przypadku zostaną wykonane co najmniej \(N^2\) akcje. Oszacowanie \(O(N^3)\) gwarantuje, że najgorszym przypadkiem będzie nie więcej niż uporządkowanie działań \(N^3\). Stosowane jest również oszacowanie \(\Theta(N)\), które jest górnym i dolnym oszacowaniem asymptotycznym, gdy\(O(N)\) i \(\Omega(N)\) są takie same.Zatem \(O(N)\) jest przybliżonym oszacowaniem algorytmu na najgorszych danych wejściowych,\(\Omega(N)\) - na najlepszych danych wejściowych,\(\Theta(N)\) - skrócony zapis identyczności\(O(N)\) i \(\Omega(N)\).
Szacunki czasu działania dla różnych algorytmów
Oznaczmy T(N) jako czas wykonania algorytmu. Niech badany algorytm będzie miał postać:
1. zestaw instrukcji obejmujący jedynie podstawowe operacje:
Oświadczenie 1;
...
stwierdzenie k;
Wtedy T(N) = T(stwierdzenie 1) + ... + T(stwierdzenie k).
Ponieważ Każda instrukcja zawiera jedynie podstawowe operacje, wówczas czas wykonania tego fragmentu kodu nie jest zależny od wielkości danych wejściowych (nie zwiększa się wraz z wielkością danych wejściowych), tj. jest stałą. Algorytm ten ma złożoność O(1).
2. instrukcje if-else
Jeśli (warunek) (
sekwencja stwierdzeń 1
}
w przeciwnym razie(
sekwencja zdań 2
}
W tym przypadku zostanie wykonana albo sekwencja instrukcji 1, albo sekwencja instrukcji 2, ponieważ chcemy oszacować czas wykonania najgorszego przypadku, T(N) = max(T(sekwencja instrukcji 1), T(sekwencja instrukcji 2)). Na przykład, jeśli czas wykonania sekwencji instrukcji 1 wynosi O(N), a sekwencja instrukcji to O(1), to T(N) = O(N).
Dla (i = 0; tj< N; i++) {
sekwencja wypowiedzi
}
Ponieważ pętla zostanie wykonana N razy, wówczas sekwencja instrukcji również zostanie wykonana N razy. Jeżeli T(ciąg instrukcji) = O(1), to T(N) = O(N)*O(1) = O(N).
4. Zagnieżdżone pętle.
Dla (i = 0; tj< N; i++) {
dla (j = 0; j< M; j ++){
...
}
}
Pętla zewnętrzna jest wykonywana N razy. Za każdym razem, gdy wykonywana jest pętla zewnętrzna, wykonywana jest pętla wewnętrzna M Teraz rozważ ten kod: Dla (i = 0; tj< N; i++) { Przyjrzyjmy się zmianie liczby iteracji pętli wewnętrznej w zależności od iteracji pętli zewnętrznej. I cykl j (liczba czasów wykonania) Następnie sekwencja instrukcji zostanie wykonana N + N-1 + ... + 1 razy. Do szybkiego obliczenia takich kwot przydatne są wzory z analizy matematycznej, w tym przypadku wzór
A oto inne najczęściej potrzebne formuły przydatne w takich przypadkach: 4. Jeżeli asercja zawiera wywołanie metody, szacunkowy czas wykonania asercji jest obliczany z uwzględnieniem oszacowanego czasu wykonania metody. Na przykład: dla (j = 0; j< N; j ++){ 5. Wyszukiwanie binarne (binarne). Całkowite l = 0; Wyszukiwanie binarne pozwala znaleźć indeks liczby k w posortowanej tablicy; jeśli tej liczby w niej nie ma, zwracane jest -1. Najpierw porównujemy k z liczbą w środku tablicy. Jeśli k jest mniejsze od tej liczby, to musimy go dalej szukać w lewej połowie tablicy, jeśli jest więcej, to w prawej połowie. Następnie k jest porównywane z liczbą znajdującą się w środku połowy tablicy wybranej w poprzednim kroku itd. Z każdą iteracją przestrzeń poszukiwań zmniejsza się o połowę. Powstaje pytanie: ile iteracji trzeba będzie wykonać w najgorszym przypadku (to znaczy, gdy w tablicy nigdy nie zostanie znaleziona liczba równa k i nie ma już danych do porównania). Widzimy, że po 1 iteracji zostaną \(N/2\) dane do wyszukiwania indeksu \(k\), po 2 iteracjach zostaną \(N/4\) dane, po 3 iteracjach - \( N/8\) itd. Liczbę iteracji poznamy w najgorszym przypadku, jeśli rozwiążemy równanie \(\frac(N)(2^x)=1\). Równanie to jest równoważne równaniu \(2^x=N\), stąd \(x=log_(2)(N)\) lub \(x=log(N)\) (patrz definicja logarytmu). Dlatego oszacowanie złożoności algorytmu wyszukiwania binarnego wynosi \(O(logN)\). Dobra wiadomość jest taka, że do scharakteryzowania czasu wykonania większości algorytmów wystarczy kilka funkcji: \(1, logN, N, NlogN, N^2, N^3, 2^N\). Wykres ilustruje różne szybkości wzrostu czasu wykonania algorytmu w zależności od wielkości danych wejściowych: W szczególności z tego wykresu jasno wynika, że jeśli czas wykonania algorytmu jest „logarytmiczny”, tj. algorytm ma złożoność \(O(logN)\), to jest to bardzo fajne, ponieważ jego czas wykonania rośnie bardzo wolno wraz ze wzrostem rozmiaru danych wejściowych, jeśli czas wykonania zależy liniowo od rozmiaru danych wejściowych, to też nie jest źle, ale lepiej nie używać algorytmów o wykładniczym czasie działania (\( O(2^N)\)) lub używaj tylko w przypadku bardzo małych rozmiarów danych. klasy P i NP Rzeczywista nieujemna funkcja \(f(m)\), zdefiniowana dla dodatnich wartości całkowitych argumentu, nazywana jest ograniczoną wielomianem, jeśli istnieje wielomian \(P(m)\) o rzeczywistych współczynnikach takich jak \( f(m) \leq P( m)\) dla wszystkich \(m \in N^+\). Zadania, dla których istnieją algorytmy z czasem wykonania „wielomianowym”, należą do klasy P (problemy te na ogół rozwiązywane są szybko i bezproblemowo). Definicja formalna. Język L należy do klasy P wtedy i tylko wtedy, gdy istnieje deterministyczna maszyna Turinga M taka, że: Dla dowolnych danych wejściowych M kończy pracę w czasie wielomianowym, Problemy klasy NP- zadania spełniające warunek: jeśli istnieje odpowiedź (możliwe rozwiązanie), to łatwo ją zweryfikować - sprawdź, czy jest to rozwiązanie, czy nie. Rozważmy przykład problemu z klasy NP. Niech zostanie podany zbiór liczb całkowitych, na przykład (-7, -3, -2, 5, 8). Musisz dowiedzieć się, czy wśród tych liczb są 3 liczby, które w sumie dają 0. W tym przypadku odpowiedź brzmi „tak” (na przykład taka trójka to liczby (-3,-2,5). rośnie wielkość zbiorów liczb całkowitych, liczba podzbiorów składających się z 3 elementów rośnie wykładniczo. Tymczasem jeśli mamy dany jeden taki podzbiór (zwany także certyfikatem), to możemy łatwo sprawdzić, czy suma jego elementów jest równy 0. Formalna definicja: Język L należy do klasy NP wtedy i tylko wtedy, gdy istnieją wielomiany \(p\) i \(q\) oraz deterministyczna maszyna Turinga M taka, że: Dla dowolnego \(x,y\) maszyna M na danych wejściowych \((x,y)\) wykonuje się w czasie \(p(|x|)\), Redukowalność wielomianu lub redukowalność Karpa. Funkcja \(f_1\) sprowadza się do funkcji \(f_2\), jeśli istnieje funkcja \(f \in P\) taka, że dla dowolnego \(x\) \(f_(1)(x)=f_( 2 )(f(x))\). Nazywa się problem T NP-twardy, jeśli dla niego istnieje problem NP-zupełny, który redukuje się do T w czasie wielomianowym. Mamy tu na myśli redukowalność Cooka. Redukcja Cooka problemu \(R_1\) do \(R_2\) jest wielomianowym algorytmem czasu rozwiązującym problem \(R_1\) pod warunkiem, że funkcja znajdująca rozwiązanie problemu \(R_2\) jest mu dana w postaci wyroczni , czyli uzyskanie do niego dostępu zajmuje tylko jeden krok. Oto możliwe zależności pomiędzy powyższymi klasami problemów (naukowcy wciąż nie są pewni, czy P i NP to to samo). Funkcja trudności 0(1). W algorytmach o stałej złożoności większość operacji w programie wykonywana jest jeden lub więcej razy. Każdy algorytm, który zawsze wymaga (niezależnie od rozmiaru danych) tej samej ilości czasu, ma stałą złożoność. Funkcja złożoności 0(N). Czas działania programu jest zwykle liniowy, a każdy element danych wejściowych musi zostać przetworzony tylko liniową liczbę razy. Ta funkcja złożoności charakteryzuje cykl prosty. Funkcja złożoności 0(N 2), 0(N 3), 0(№) -
funkcja złożoności wielomianowej: liczba operacji rośnie wraz z kwadratem N. W ogólnym przypadku może to być O(A^), w zależności od złożoności problemu. Ta funkcja złożoności charakteryzuje cykl złożony. Funkcja trudności O(log2 (A0), 0(N log2(A0). To czas, kiedy działają algorytmy, które dzielą duży problem na wiele małych, a następnie po ich rozwiązaniu łączą rozwiązania. Funkcja złożoności 0(e N). Algorytmy o złożoności wykładniczej najczęściej wynikają z podejścia zwanego brutalną siłą. Funkcja złożoności 0(M) - liczba operacji rośnie proporcjonalnie do silni N. Programista musi umieć analizować algorytmy i określać ich złożoność. Złożoność czasową algorytmu można obliczyć na podstawie analizy jego struktur sterujących. Algorytmy bez pętli i wywołań rekurencyjnych mają stałą złożoność. Jeśli nie ma rekurencji i pętli, wszystkie struktury sterujące można sprowadzić do struktur o stałej złożoności. W związku z tym cały algorytm charakteryzuje się również stałą złożonością. Określenie złożoności algorytmu sprowadza się głównie do analizy pętli i wywołań rekurencyjnych. Rozważmy na przykład algorytm przetwarzania elementów tablicy. Dla /": = 1 do N zacznij Złożoność tego algorytmu O(A), ponieważ treść pętli jest wykonywana A razy, a złożoność treści pętli wynosi 0(1). Jeśli jedna pętla jest zagnieżdżona w drugiej i obie pętle zależą od wielkości tej samej zmiennej, wówczas cały projekt charakteryzuje się złożonością kwadratową. Dla /: = 1 do N zrobić dla j: = 1 do N zacznij Złożoność tego programu 0(N2). Przykład 1. Oszacujmy złożoność programu, który wprowadza tablicę z klawiatury i znajduje w niej największy element. Algorytm składa się z następujących kroków: Dodajmy liczbę operacji A + (A - 1) + 1 = 2A, tj. istnieje taką stałą, że dla dowolnego A liczba operacji nie przekracza CA. Zatem złożoność algorytmu wynosi 0(A). Przykład 2. Oszacujmy złożoność programu, który wprowadza tablicę z klawiatury i znajduje w niej element o danej właściwości (np. równej określonej wartości). Algorytm składa się z następujących kroków: W najlepszym przypadku podany algorytm będzie wymagał operacji A+2 (wejście całej tablicy, pojedyncze porównanie, wyjście), w najgorszym przypadku (gdy takiego elementu nie ma, operacja 2A+1). Jeśli A jest dużą liczbą, na przykład rzędu 10 6, wówczas można zaniedbać jedność. Zatem złożoność algorytmu jest równa 0(N). Przykład 3. Zdefiniujmy funkcję złożoności algorytmu szyfrowania dla słowa o długości L metodą podstawieniową. Niech będzie tabela, w której dla każdego znaku alfabetu zapisany zostanie znak, na który należy go zastąpić. Oznaczmy liczbę liter alfabetu S. Algorytm składa się z następujących kroków: Całkowita liczba operacji 1 + (S+)L. W przypadku odpowiednio dużego S I L jednostki można pominąć i okazuje się, że funkcja złożoności danego algorytmu wynosi O(SL). Przykład 4. Zdefiniujmy funkcję złożoności algorytmu translacji liczb naturalnych 1
V do systemu liczb binarnych (bez operacji wprowadzania i wyprowadzania danych). Algorytm składa się z następujących kroków: Całkowita liczba operacji nie przekracza 1 + log 2 A. Dlatego opisywany algorytm ma złożoność 0(og 2 N). Dla każdego programisty ważna jest znajomość podstaw teorii algorytmów, ponieważ to właśnie ta nauka bada ogólną charakterystykę algorytmów i formalne modele ich reprezentacji. Już od lekcji informatyki uczono nas tworzenia schematów blokowych, które później pomagają w pisaniu bardziej złożonych problemów niż w szkole. Nie jest też tajemnicą, że prawie zawsze istnieje kilka sposobów rozwiązania konkretnego problemu: niektóre wymagają poświęcenia dużej ilości czasu, inne zasobów, a jeszcze inne pomagają jedynie w przybliżeniu znaleźć rozwiązanie. Zawsze należy szukać optymalnego rozwiązania zgodnie z zadaniem, w szczególności podczas opracowywania algorytmów rozwiązywania danej klasy problemów. W tym artykule proponuję opisać główne kryteria oceny i podać przykład oceny prostego algorytmu. Habrahabr posiada już informacje na temat metod oceny algorytmów, jednak są one skierowane głównie do uczniów szkół średnich. Niniejszą publikację można uznać za rozwinięcie tego artykułu. Głównym wskaźnikiem złożoności algorytmu jest czas potrzebny na rozwiązanie problemu i ilość wymaganej pamięci. Istnieją koncepcje złożoności w najgorsze, przeciętny Lub najlepszy scenariusz. Zwykle złożoność ocenia się w najgorszym przypadku. Złożoność czasowa w najgorszym przypadku jest to funkcja wielkości wejściowej, równa maksymalnej liczbie operacji wykonywanych podczas działania algorytmu przy rozwiązywaniu problemu o danej wielkości. Kolejność rosnącego stopnia trudności(lub złożoność aksjomatyczna) opisuje przybliżone zachowanie funkcji złożoności algorytmu, gdy rozmiar danych wejściowych jest duży. Wynika z tego, że przy szacowaniu złożoności czasowej nie trzeba uwzględniać operacji elementarnych, wystarczy uwzględnić kroki algorytmu. Krok algorytmu– zbiór sekwencyjnie ułożonych operacji elementarnych, których czas wykonania nie zależy od wielkości wejścia, czyli jest ograniczony od góry pewną stałą. Rozważ złożoność f(n) > 0, funkcja tego samego rzędu g(n) > 0, wielkość wejścia n > 0. Funkcja g(n) w tym przypadku jest asymptotycznie dokładnym oszacowaniem f(n). Jeżeli f(n) jest funkcją złożoności algorytmu, to rząd złożoności definiuje się jako f(n) – O(g(n)). To wyrażenie definiuje klasę funkcji, które rosną nie szybciej niż g(n) aż do stałego współczynnika. Definicja jest jednak podobna do szacunków najgorszego przypadku Ω(g(n)) definiuje klasę funkcji, które rosną nie wolniej niż sama funkcja g(n) aż do stałego współczynnika. Warto tylko wspomnieć, że w tym przypadku jest to funkcja f(n) Na n > n 0 wszędzie jest pomiędzy do 1 *g(n) I do 2 *g(n), gdzie c jest czynnikiem stałym. Jednolite kryterium wagowe (UWC) zakłada, że każdy krok algorytmu wykonywany jest w jednej jednostce czasu, a komórka pamięci w jednej jednostce objętości (aż do stałej). Trudność czasowa dla DEX określona przez wartość poobcinać), Gdzie O str– wartość operandu. Należy przeanalizować złożoność algorytmu obliczeń silniowych. Aby to zrobić, napiszmy to zadanie w pseudokodzie C: Void main() ( int wynik = 1; int i; const n = ...; for (i = 2; i<= n; i++)
result = result * n;
}
Wystarczy po prostu ustalić, że wielkość wejściowa danego problemu wynosi N. Zatem złożoność czasowa w ramach RVC jest równa NA). W tym momencie należy wyróżnić operacje, które wymagają oceny. Po pierwsze, są to operacje porównawcze. Po drugie, operacje zmiany zmiennych (dodawanie, mnożenie). Operacje przypisania nie są brane pod uwagę, ponieważ zakłada się, że są natychmiastowe. Zatem w tym zadaniu są trzy operacje: Okazuje się, że na i-tym kroku log(n). Okazuje się, że na i-tym kroku log(i). Okazuje się, że na i-tym kroku log((i-1)!). Jeśli dodasz wszystkie powstałe wartości i odrzucisz terminy, które oczywiście rosną wolniej wraz ze wzrostem N, otrzymujemy końcowe wyrażenie Tutaj wszystko jest proste. Konieczne jest policzenie liczby zmiennych. Jeśli problem wykorzystuje tablice, każda komórka tablicy jest uważana za zmienną. W takim przypadku należy wziąć pod uwagę maksymalną wartość, jaką można zapisać w komórce pamięci. Jeśli wartość jest niezdefiniowana (na przykład, gdy operand i > 10), wówczas zakłada się, że istnieje jakiś rodzaj wartości granicznej Vmaks. Badanie złożoności algorytmów jest dość fascynującym zadaniem. Obecnie analiza najprostszych algorytmów jest uwzględniona w programach nauczania specjalności technicznych (dokładniej uogólnionego kierunku „Informatyka i Informatyka”) zajmujących się informatyką i matematyką stosowaną w zakresie informatyki. Cześć! Dzisiejszy wykład będzie nieco inny od pozostałych. Będzie się różnić tym, że jest tylko pośrednio powiązany z Javą. Temat ten jest jednak bardzo ważny dla każdego programisty. Porozmawiamy o algorytmy. Co to jest algorytm? Krótko mówiąc, jest to pewna sekwencja działań, które należy wykonać, aby osiągnąć pożądany rezultat. Często używamy algorytmów w życiu codziennym. Na przykład każdego ranka stajesz przed zadaniem: przyjść do szkoły lub pracy, a jednocześnie być:
dla (j = ja + 1; j< N; j ++){
sekwencja wypowiedzi
}
}
0 N
1 N-1
2 N-2
...
N-1 1
Te. ten algorytm będzie miał złożoność \(O(N^2)\).
Jeżeli czas wykonania metody wynosi \(g(N)=O(N)\), to \(T(N) = O(N)*O(N) = O(N^2)\).
int u = A.długość - 1
int m;
podczas gdy (l<= u) {
m = l + (u - 1)/2
jeśli A[m]< k {
l = m +1;
}
w przeciwnym razie A[m] == k (
zwróć m;
}
w przeciwnym razie(
u = m - 1;
}
}
zwróć -1;
- dla wszystkich \(x \in L\) M daje wynik 1,
- dla wszystkich \(x\) nie należących do \(L\), M daje wynik 0.
- dla dowolnego \(x \in L\) istnieje ciąg \(y\) o długości \(q(|x|)\) taki, że \(M(x,y)=1\),
- dla dowolnego \(x\) nie z \(L\) i wszystkich ciągów o długości \(q(|x|)\) \(M(x,y)=0\).
Nazywa się problem T NP-kompletny, jeśli należy do klasy NP i każdy inny problem z NP można do niego sprowadzić w czasie wielomianowym. Być może najbardziej znanym przykładem problemu NP-zupełnego jest problem SAT (od słowa spełnialność). Otrzymamy formułę zawierającą zmienne logiczne, operatory „AND”, „OR”, „NOT” i nawiasy. Problem polega na tym, czy można przypisać wartości wszystkim zmiennym występującym w formule? kłamstwo I PRAWDA aby formuła przyjęła wartość „ PRAWDA".
Ważne jest również, aby ocenić, jak algorytm będzie się zachowywał przy początkowych wartościach różnych objętości i ilości, jakich zasobów będzie potrzebował i ile czasu zajmie wygenerowanie wyniku końcowego.
Jest to przedmiotem gałęzi teorii algorytmów – teorii asymptotycznej analizy algorytmów.Definicje
Ponadto analizując złożoność klasy problemów, określa się pewną liczbę, która charakteryzuje pewną ilość danych - wielkość wejścia.
Możemy więc tak stwierdzić złożoność algorytmu jest funkcją wielkości wejścia.
Złożoność algorytmu może być różna dla tego samego rozmiaru wejściowego, ale różnych danych wejściowych.
Złożoność pojemnościowa w najgorszym przypadku funkcja wielkości wejściowej równa maksymalnej liczbie komórek pamięci, do których uzyskano dostęp podczas rozwiązywania problemów o danym rozmiarze.Rząd rosnącej złożoności algorytmów
Rodzaje estymatorów asymptotycznych
O – ocena najgorszego przypadku
Jeśli f(n) = O(g(n)) i istnieją stałe c > 0, n 0 > 0, To
0 < f(n) < c*g(n),
Dla n > n 0.Przykłady funkcji asymptotycznych
f(n)
g(n)
2n 2 + 7n - 3
nr 2
98n*ln(n)
n*ln(n)
5n+2
N
8
1
Ω – oszacowanie dla najlepszego przypadku
f(n) = Ω(g(n)), Jeśli
0 < c*g(n) < f(n)
Θ – oszacowanie dla przypadku przeciętnego
Na przykład kiedy f(n) = n 2 + n; g(n) = n 2.Kryteria oceny złożoności algorytmów
Logarytmiczne kryterium wagi (LWC) uwzględnia rozmiar operandu przetwarzanego w ramach określonej operacji oraz wartość przechowywaną w komórce pamięci.
Złożoność pojemnościowa w LVK określona przez wartość l(M), Gdzie M– wielkość komórki pamięci.Przykład oszacowania złożoności przy obliczaniu silni
Złożoność czasowa przy jednolitym kryterium ważenia
Liczba kroków – (n - 1).Złożoność czasowa przy logarytmicznym kryterium ważenia
1) I<= n
Od kroków (n-1), złożoność tej operacji będzie (n-1)*log(n).2) ja = ja + 1
.3) wynik = wynik * tj
Zatem suma jest 
.
.Złożoność pojemnościowa przy jednolitym kryterium wagowym
Ponieważ liczba zmiennych nie zależy od wielkości danych wejściowych, złożoność będzie równa O(1).Złożoność pojemnościowa z logarytmicznym kryterium wagowym
W tym zadaniu występuje zmienna, której wartość nie przekracza n(i) oraz zmienną, której wartość nie przekracza N! (wynik). Więc wynik jest O(log(n!)).wnioski
Ze względu na złożoność wyróżnia się różne klasy zadań: P, NP, NPC. Ale nie stanowi to już problemu w teorii asymptotycznej analizy algorytmów.
Który algorytm pozwoli Ci osiągnąć taki wynik?
Ta sekwencja działań z pewnością pozwoli Ci uzyskać pożądany rezultat. W programowaniu cały sens naszej pracy polega na ciągłym rozwiązywaniu problemów. Znaczącą część tych zadań można wykonać wykorzystując znane już algorytmy. Na przykład stoisz przed zadaniem: posortuj listę 100 nazw w tablicy. To zadanie jest dość proste, ale można je rozwiązać na różne sposoby. Oto jedno rozwiązanie: Algorytm sortowania nazw alfabetycznie:
Czy taka sekwencja działań pozwoli nam rozwiązać nasz problem? Tak, całkowicie na to pozwoli. Czy to będzie rozwiązanie skuteczny? Ledwie. Tutaj dochodzimy do kolejnej bardzo ważnej właściwości algorytmów – ich efektywność. Problem można rozwiązać na różne sposoby. Ale zarówno w programowaniu, jak i w życiu codziennym wybieramy metodę, która będzie najskuteczniejsza. Jeśli Twoim zadaniem jest zrobienie kanapki z masłem, możesz oczywiście zacząć od zasiania pszenicy i wydojenia krowy. Ale tak będzie nieskuteczny rozwiązanie - zajmie to bardzo dużo czasu i będzie kosztować dużo pieniędzy. Aby rozwiązać swój prosty problem, możesz po prostu kupić chleb i masło. A algorytm z pszenicą i krową, choć pozwala rozwiązać problem, jest zbyt skomplikowany, aby zastosować go w praktyce. Aby ocenić złożoność algorytmów w programowaniu, stworzono specjalną notację tzw Duże-O („duże O”).
Big-O pozwala oszacować, w jakim stopniu czas wykonania algorytmu zależy od przekazanych do niego danych. Spójrzmy na najprostszy przykład – transfer danych. Wyobraź sobie, że musisz przesłać jakąś informację w formie pliku na dużą odległość (na przykład 5000 kilometrów). Który algorytm będzie najskuteczniejszy? To zależy od danych, z którymi musi pracować. Na przykład mamy plik audio o rozmiarze 10 megabajtów. 
W tym przypadku najskuteczniejszym algorytmem byłoby przesłanie pliku przez Internet. Zajmie to tylko kilka minut! Wypowiedzmy więc jeszcze raz nasz algorytm: „Jeśli chcesz przesłać informacje w postaci plików na odległość 5000 kilometrów, musisz skorzystać z transmisji danych przez Internet”. Świetnie. Teraz to przeanalizujmy. Czy to rozwiązuje nasz problem? Ogólnie tak, całkowicie to rozwiązuje. Ale co możesz powiedzieć o jego złożoności? Hmm, teraz sprawa robi się interesująca. Faktem jest, że nasz algorytm w dużej mierze zależy od napływających danych, a mianowicie od rozmiaru plików. Teraz mamy 10 megabajtów i wszystko jest w porządku. A co jeśli będziemy musieli przesłać 500 megabajtów? 20 gigabajtów? 500 terabajtów? 30 petabajtów? Czy nasz algorytm przestanie działać? Nie, wszystkie te ilości danych nadal można przesyłać. Czy ukończenie zajmie więcej czasu? Tak, to będzie! Teraz znamy ważną cechę naszego algorytmu: Im większy rozmiar danych do przesłania, tym dłużej trwa algorytm.. Chcielibyśmy jednak dokładniej zrozumieć, jak wygląda ta zależność (pomiędzy wielkością danych a czasem potrzebnym na ich przesłanie). W naszym przypadku złożoność algorytmu będzie wynosić liniowy. „Liniowy” oznacza, że wraz ze wzrostem objętości danych czas ich transmisji będzie się wydłużał w przybliżeniu proporcjonalnie. Jeśli danych jest 2 razy więcej, a ich przesłanie zajmie 2 razy więcej czasu. Jeśli danych jest 10 razy więcej, czas przesyłania wzrośnie 10 razy. Używając notacji Big-O, złożoność naszego algorytmu jest dana wzorem NA). Zapis ten najlepiej zapamiętać do wykorzystania w przyszłości – zawsze stosuje się go w przypadku algorytmów o złożoności liniowej. Uwaga: wcale nie mówimy tutaj o różnych „zmiennych” rzeczach: szybkości Internetu, mocy naszego komputera i tak dalej. Oceniając złożoność algorytmu, to po prostu nie ma sensu – i tak nie mamy na to wpływu. Big-O ocenia sam algorytm, niezależnie od „środowiska”, w którym będzie musiał pracować. Kontynuujmy nasz przykład. Załóżmy, że ostatecznie okaże się, że rozmiar plików do przesłania wynosi 800 terabajtów. Jeśli prześlemy je przez Internet, problem oczywiście zostanie rozwiązany. Jest tylko jeden problem: transmisja po standardowym, nowoczesnym łączu (100 megabitów na sekundę), z którego większość z nas korzysta w domach, zajmie około 708 dni. Prawie 2 lata! :O Zatem nasz algorytm najwyraźniej nie jest tutaj odpowiedni. Potrzebujemy innego rozwiązania! Nagle z pomocą przychodzi nam gigant IT Amazon! Usługa Amazon Snowmobile pozwala załadować duże ilości danych do mobilnych jednostek magazynujących i dostarczyć je pod wskazany adres ciężarówką! 
Mamy więc nowy algorytm! „Jeśli potrzebujesz przesłać informacje w formie plików na odległość 5000 kilometrów, a w przypadku przesyłania przez Internet proces ten będzie trwał dłużej niż 14 dni, warto skorzystać z transportu ciężarowego Amazon.” Liczba 14 dni została tu wybrana losowo: powiedzmy, że jest to maksymalny okres, na jaki nas stać. Przeanalizujmy nasz algorytm. A co z prędkością? Nawet jeśli ciężarówka jedzie z prędkością zaledwie 50 km/h, 5000 kilometrów pokona w zaledwie 100 godzin. To nieco ponad cztery dni! Jest to znacznie lepsze rozwiązanie niż opcja transmisji internetowej. A co ze złożonością tego algorytmu? Czy będzie to również liniowe, O(N)? Nie, nie będzie. W końcu ciężarówka nie dba o to, ile ją załadujesz - nadal będzie jechała z mniej więcej tą samą prędkością i dotrze na czas. Niezależnie od tego, czy mamy 800 terabajtów, czy 10 razy więcej danych, ciężarówka i tak dotrze tam w 5 dni. Innymi słowy algorytm dostarczania danych ciężarówką ciągłe trudności. „Stała” oznacza, że nie jest ona zależna od danych przekazywanych do algorytmu. Włóż do ciężarówki pendrive o pojemności 1 GB, a przyjedzie w ciągu 5 dni. Umieść tam dyski z 800 terabajtami danych, a przyjdą za 5 dni. Podczas korzystania z Big-O stałą złożoność oznacza się jako O(1). Odkąd się poznaliśmy NA) I O(1), spójrzmy teraz na więcej przykładów „programistycznych” :) Załóżmy, że masz tablicę 100 liczb i zadaniem jest wypisanie każdej z nich na konsolę. Piszesz zwykłą pętlę for, która wykonuje to zadanie int number = new int [100]; // ..wypełnij tablicę liczbami for (int i: number) ( System. out. println (i) ; ) Jaka jest złożoność zapisanego algorytmu? Liniowy, O(N). Liczba akcji, które program musi wykonać, zależy od tego, ile dokładnie liczb zostało do niego przekazanych. Jeśli w tablicy będzie 100 liczb, będzie 100 akcji (wyjście na ekranie).Jeśli w tablicy będzie 10 000 liczb, trzeba będzie wykonać 10 000 akcji. Czy można ulepszyć nasz algorytm? NIE. W każdym razie będziemy musieli to zrobić N przechodzi przez tablicę i wykonaj N wyjść na konsolę. Spójrzmy na inny przykład. public static void main(String args) (LinkedList <
Integer>
liczby = nowa lista połączona<
>() ; liczby. dodaj(0, 20202); liczby. dodaj(0, 123); liczby. dodaj(0, 8283); ) Mamy pustą listę LinkedList, do której wstawiamy pewne liczby. Musimy oszacować złożoność algorytmu wstawiania pojedynczej liczby do listy LinkedList w naszym przykładzie i to, jak zależy to od liczby elementów na liście. Odpowiedź będzie O(1) - stała złożoność. Dlaczego? Uwaga: każdorazowo wstawiamy cyfrę na początku listy. Dodatkowo, jak pamiętasz, kiedy wstawisz liczbę do LinkedList, elementy nigdzie się nie przesuwają - linki są przedefiniowane (jeśli nagle zapomniałeś, jak działa LinkedList, spójrz na jeden z naszych). Jeśli teraz pierwszą liczbą na naszej liście jest liczba x, a na początku listy wstawimy liczbę y, wystarczy x. poprzedni = y; y. poprzedni = null; y. następny = x; W przypadku tego zastąpienia odniesienia nie obchodzi nas, ile numerów znajduje się teraz na LinkedList- co najmniej jeden, co najmniej miliard. Złożoność algorytmu będzie stała - O(1). Złożoność logarytmiczna
Nie panikować! :) Jeśli słowo „logarytmiczny” sprawia, że chcesz zamknąć wykład i nie czytać dalej, poczekaj kilka minut. Nie będzie tu żadnych trudności matematycznych (jest mnóstwo takich wyjaśnień w innych miejscach), a wszystkie przykłady przeanalizujemy „na palcach”. Wyobraź sobie, że Twoim zadaniem jest znalezienie jednej konkretnej liczby w tablicy składającej się ze 100 liczb. A dokładniej sprawdź, czy w ogóle tam jest. Po znalezieniu żądanego numeru należy przerwać wyszukiwanie, a w konsoli powinien wyświetlić się wpis „Znaleziono żądany numer!”. Jego indeks w tablicy =...”. Jak rozwiązałbyś taki problem? Tutaj rozwiązanie jest oczywiste: należy iterować po elementach tablicy, zaczynając od pierwszego (lub ostatniego) i sprawdzać, czy aktualna liczba pokrywa się z żądaną. W związku z tym liczba działań zależy bezpośrednio od liczby elementów w tablicy. Jeśli mamy 100 liczb, musimy 100 razy przejść do następnego elementu i 100 razy sprawdzić liczbę. Jeśli będzie 1000 liczb, wówczas będzie 1000 kroków kontrolnych. Jest to oczywiście złożoność liniowa, NA). Teraz dodamy jedno wyjaśnienie do naszego przykładu: tablica, w której należy znaleźć liczbę, jest posortowana w kolejności rosnącej. Czy to coś zmienia dla naszego zadania? Nadal możemy wyszukać żądany numer brutalną siłą. Ale zamiast tego możemy użyć dobrze znanego Algorytm wyszukiwania binarnego.
W górnym wierszu obrazu widzimy posortowaną tablicę. Musimy w nim znaleźć liczbę 23. Zamiast iterować po liczbach, po prostu dzielimy tablicę na 2 części i sprawdzamy średnią liczbę w tablicy. Znajdujemy liczbę znajdującą się w komórce 4 i sprawdzamy ją (drugi rząd na obrazku). Ta liczba to 16, a my szukamy 23. Obecna liczba jest mniejsza. Co to znaczy? Co wszystkie poprzednie liczby (które znajdują się przed liczbą 16) nie muszą być sprawdzane: na pewno będą mniejsze niż te, których szukamy, ponieważ nasza tablica jest posortowana! Kontynuujmy poszukiwania wśród pozostałych 5 elementów. Uwaga: przeprowadziliśmy tylko jedną kontrolę, ale wyeliminowaliśmy już połowę możliwych opcji. Zostało nam już tylko 5 elementów. Powtórzymy nasz krok - ponownie podziel pozostałą tablicę przez 2 i ponownie weź środkowy element (linia 3 na rysunku). Ta liczba wynosi 56 i jest większa niż ta, której szukamy. Co to znaczy? Że odrzucimy jeszcze 3 opcje - samą liczbę 56 i dwie liczby po niej (są zdecydowanie większe niż 23, ponieważ tablica jest posortowana). Do sprawdzenia pozostały nam już tylko 2 liczby (ostatni wiersz na rysunku) - liczby z indeksami tablicy 5 i 6. Sprawdzamy pierwszą z nich i właśnie tego szukaliśmy - liczby 23! Jego indeks = 5! Przyjrzyjmy się wynikom naszego algorytmu, a wtedy zrozumiemy jego złożoność. (Nawiasem mówiąc, teraz rozumiesz, dlaczego nazywa się to binarnym: jego istotą jest ciągłe dzielenie danych przez 2). Wynik jest imponujący! Gdybyśmy szukali żądanej liczby za pomocą wyszukiwania liniowego, potrzebowalibyśmy 10 kontroli, ale przy wyszukiwaniu binarnym zrobiliśmy to w 3! W najgorszym przypadku byłoby ich 4, gdyby na ostatnim etapie potrzebna nam liczba okazała się drugą, a nie pierwszą. A co z jego złożonością? To bardzo interesująca kwestia :) Algorytm wyszukiwania binarnego zależy w znacznie mniejszym stopniu od liczby elementów w tablicy niż algorytm wyszukiwania liniowego (czyli prostego wyliczenia). Na 10
elementów tablicy, wyszukiwanie liniowe będzie wymagało maksymalnie 10 kontroli, a wyszukiwanie binarne będzie wymagało maksymalnie 4 kontroli. Różnica jest 2,5 razy. Ale dla tablicy in 1000 elementów wyszukiwanie liniowe będzie wymagało 1000 kontroli, a wyszukiwanie binarne będzie wymagało łącznie 10! Różnica jest już 100-krotna! Uwaga: liczba elementów tablicy wzrosła 100-krotnie (z 10 do 1000), ale liczba niezbędnych sprawdzeń w wyszukiwaniu binarnym wzrosła tylko 2,5-krotnie - z 4 do 10. Jeśli dotrzemy do 10000 elementów, różnica będzie jeszcze bardziej imponująca: 10 000 kontroli w przypadku wyszukiwania liniowego i tylko 14 kontroli dla binarnego. I znowu: liczba elementów wzrosła 1000 razy (z 10 do 10 000), ale liczba kontroli wzrosła tylko 3,5 razy (z 4 do 14). Złożoność algorytmu wyszukiwania binarnego jest logarytmiczna lub, jeśli użyjemy notacji Big-O, - O(log n). Dlaczego tak się nazywa? Logarytm jest odwrotnością podniesienia do potęgi. Logarytm binarny służy do obliczania potęgi liczby 2. Na przykład mamy 10 000 elementów, które musimy sprawdzić za pomocą wyszukiwania binarnego. 
Teraz masz obraz przed oczami i wiesz, że wymaga to maksymalnie 14 kontroli. Ale co, jeśli nie masz obrazu przed oczami i musisz policzyć dokładną liczbę niezbędnych kontroli? Wystarczy odpowiedzieć na proste pytanie: Do jakiej potęgi należy podnieść liczbę 2, aby otrzymany wynik wynosił >= liczba sprawdzanych elementów? Dla 10000 będzie to potęga 14. 2 do potęgi 13 to za mało (8192) Ale 2 do potęgi 14 = 16384, liczba ta spełnia nasz warunek (jest to >= liczba elementów w tablicy). Znaleźliśmy logarytm - 14. Dokładnie tyle kontroli potrzebujemy! :) Algorytmy i ich złożoność to temat zbyt obszerny, aby ująć go w jednym wykładzie. Ale wiedza o tym jest bardzo ważna: w wielu rozmowach kwalifikacyjnych pojawią się problemy algorytmiczne. Dla teorii mogę polecić Ci kilka książek. Dobrym miejscem na rozpoczęcie jest „Wideo Big-O na YouTube”. Do zobaczenia na kolejnych wykładach! :)
