złożoność algorytmiczna. Algorytmy wyszukiwania

Z pewnością często spotykasz się z notacjami takimi jak O (log n) lub słyszałeś zwroty takie jak „logarytmiczna złożoność obliczeniowa” w odniesieniu do dowolnych algorytmów. A jeśli nadal nie rozumiesz, co to oznacza, ten artykuł jest dla Ciebie.

Ocena trudności

Złożoność algorytmów jest zwykle szacowana na podstawie czasu wykonania lub wykorzystanej pamięci. W obu przypadkach złożoność zależy od wielkości danych wejściowych: tablica 100 elementów zostanie przetworzona szybciej niż podobna tablica 1000. Jednocześnie niewiele osób dba o dokładny czas: zależy to od procesora, typ danych, język programowania i wiele innych parametrów. Ważna jest tylko asymptotyczna złożoność, tj. złożoność jako wielkość danych wejściowych dąży do nieskończoności.

Załóżmy, że jakiś algorytm musi wykonać 4n 3 + 7n operacji warunkowych, aby przetworzyć n elementów danych wejściowych. Wraz ze wzrostem n całkowity czas działania będzie znacznie bardziej zależny od podniesienia n do sześcianu niż pomnożenia go przez 4 lub dodania 7n. Następnie mówimy, że złożoność czasowa tego algorytmu jest równa O(n 3), czyli zależy sześciennie od wielkości danych wejściowych.

Użycie dużej litery O (lub tak zwanej notacji O) pochodzi z matematyki, gdzie używa się jej do porównania asymptotycznego zachowania funkcji. Formalnie O(f(n)) oznacza, że ​​czas działania algorytmu (lub ilość zajętej pamięci) rośnie w zależności od ilości danych wejściowych nie szybciej niż pewna stała pomnożona przez f(n) .

Przykłady

O(n) - złożoność liniowa

Taką złożoność ma na przykład algorytm znajdowania największego elementu w nieposortowanej tablicy. Musimy przejść przez wszystkie n elementów tablicy, aby dowiedzieć się, który z nich jest największy.

O(log n) - złożoność logarytmiczna

Najprostszym przykładem jest wyszukiwanie binarne. Jeśli tablica jest posortowana, możemy sprawdzić, czy zawiera konkretną wartość, dzieląc ją na pół. Sprawdźmy środkowy element, jeśli jest większy od pożądanego, to odrzucimy drugą połowę tablicy - na pewno jej tam nie ma. Jeśli mniej, to odwrotnie - odrzucamy początkową połowę. I tak dalej będziemy dzielić na pół, w efekcie sprawdzimy log n elementów.

O(n 2) - złożoność kwadratowa

Taką złożoność ma na przykład algorytm sortowania przez wstawianie. W implementacji kanonicznej składa się z dwóch zagnieżdżonych pętli: jednej do przejścia przez całą tablicę, a drugiej do znalezienia miejsca na kolejny element w już posortowanej części. Tak więc liczba operacji będzie zależeć od rozmiaru tablicy jako n * n , tj. n 2 .

Istnieją inne oceny trudności, ale wszystkie opierają się na tej samej zasadzie.

Zdarza się również, że czas działania algorytmu w ogóle nie zależy od wielkości danych wejściowych. Następnie złożoność oznaczamy jako O(1) . Na przykład, aby określić wartość trzeciego elementu tablicy, nie trzeba zapamiętywać elementów ani wielokrotnie ich powtarzać. Zawsze wystarczy poczekać na trzeci element w strumieniu danych wejściowych i będzie to wynik, którego obliczenie dla dowolnej ilości danych zajmuje tyle samo czasu.

Podobnie ocena jest przeprowadzana z pamięci, gdy jest to ważne. Jednak algorytmy mogą zużywać znacznie więcej pamięci, gdy rozmiar danych wejściowych wzrasta niż inne, ale nadal działają szybciej. I wzajemnie. Pomaga to wybrać najlepsze sposoby rozwiązywania problemów w oparciu o aktualne warunki i wymagania.

Wiemy już, że poprawność nie jest jedyną cechą, która dobry program. Jednym z najważniejszych jest efektywność, która charakteryzuje przede wszystkim czas realizacji programy dla różnych danych wejściowych (parametr ).

Znalezienie dokładnej zależności dla konkretnego programu jest dość trudnym zadaniem. Z tego powodu jest zwykle ograniczony asymptotyczne oszacowania ta funkcja, czyli opis jej przybliżonego zachowania dla dużych wartości parametru. Czasami do asymptotycznych oszacowań stosuje się tradycyjną relację (czytaj „Wielkie O”) między dwiema funkcjami , którego definicję można znaleźć w każdym podręczniku analizy matematycznej, chociaż jest ona powszechniej używana relacja równoważności(czytaj „theta big”). Jej formalna definicja znajduje się np. w książce, choć na razie wystarczy nam to zrozumieć ten przypadek W konturze.

Jako pierwszy przykład wróćmy do programów, które właśnie rozważaliśmy, do znajdowania silni liczby. Łatwo zauważyć, że liczba operacji, które należy wykonać, aby znaleźć silnię ! liczba w pierwszym przybliżeniu jest wprost proporcjonalna do tej liczby, ponieważ liczba powtórzeń cyklu (iteracji) w tym programie jest równa . W takiej sytuacji zwyczajowo mówi się, że program (albo algorytm) ma: złożoność liniowa(złożoność lub).

Czy można szybciej obliczyć silnię? Okazuje się, że tak. Możliwe jest napisanie programu, który da poprawny wynik dla tych samych wartości, dla których robią wszystkie powyższe programy, bez użycia ani iteracji, ani rekurencji. Jego złożoność będzie , co w rzeczywistości oznacza organizację obliczeń według jakiegoś wzoru bez użycia cykli i wywołań rekurencyjnych!

Nie mniej interesujący jest przykład obliczenia liczby Fibonacciego. W trakcie jej badania faktycznie już stwierdzono, że jej złożoność jest wykładniczy i równy . Takie programy praktycznie nie mają zastosowania w praktyce. Bardzo łatwo to zweryfikować, próbując obliczyć za jego pomocą 40. liczbę Fibonacciego. Z tego powodu następujący problem jest dość istotny.

Zadanie 5.4 złożoność liniowa.

Oto rozwiązanie tego problemu, w którym zmienne j i k zawierają wartości dwóch kolejnych liczb Fibonacciego.

Tekst programu

public class FibIv1 ( public static void main(String args) wyrzuca wyjątek ( int n = Xterm.inputInt("Enter n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j); ) ) )

Kolejne pytanie jest całkiem naturalne - czy można jeszcze szybciej znaleźć liczby Fibonacciego?

Po przestudiowaniu pewnych działów matematyki dość łatwo jest wyprowadzić następujący wzór na -tą liczbę Fibonacciego, który łatwo sprawdzić pod kątem małych wartości:

Mogłoby się wydawać, że na jej podstawie łatwo napisać program o złożoności, który nie wykorzystuje iteracji ani rekurencji.

Tekst programu

public class FibIv2 ( public static void main(String args) wyrzuca wyjątek ( int n = Xterm.inputInt("Enter n -> "); double f = (1.0 + Math.sqrt(5)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); ) )

W rzeczywistości ten program używa wywołania funkcji potęgowania ( Math.pow(f,n) ), której nie można zaimplementować szybciej niż w czasie logarytmicznym (). O algorytmach, w których liczba operacji jest w przybliżeniu proporcjonalna (w informatyce zwyczajowo nie wskazuje się podstawy logarytmu binarnego) mówią, że mają złożoność logarytmiczna ().

Do obliczenia liczby Fibonacciego istnieje taki algorytm, którego implementację programową podamy bez dodatkowych uwag, w przeciwnym razie trzeba będzie za dużo wyjaśniać (powiązanie liczb Fibonacciego z potęgami pewnej macierzy rzędu drugiego, przy użyciu klas do praca z macierzami, algorytm szybkiego podnoszenia macierzy do potęgi) .

Zadanie 5.5. Napisz program, który wypisuje -tą liczbę Fibonacciego, która ma złożoność logarytmiczna.

Tekst programu

public class FibIv3 ( public static void main(String args) wyrzuca wyjątek ( int n = Xterm.inputInt("Enter n -> "); Xterm.print("f(" + n + ")"); if (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( if ((n&1) == 0) ( n >>>= 1; c.square(); ) else ( n -= 1; b.mul(c); ) ) Xterm.println(" = " +b.fib()); ) ) ) klasa Matrix ( prywatne długie a, b, c, d; publiczne Matrix(długie a, długie b, długie c, długie d) ( to.a = a; to.b = b; to.c = c; to.a = a; to.b = b; to.c = c; this.d = d; ) public void mul(Matrix m) ( long a1 = a*m.a+b*mc; long b1 = a*m.b+b*md; long c1 = c*m.a+ d *mc; long d1 = c*m.b+d*md; a = a1; b = b1; c = c1; d = d1; ) public void square() ( mul(this); ) public long fib( ) ( powrót b; ) )

Jeśli spróbujesz obliczyć dziesięciomilionową liczbę Fibonacciego za pomocą tego i poprzedniego programu, różnica w czasie obliczeń będzie dość oczywista. Niestety wynik będzie niepoprawny (w obu przypadkach) ze względu na ograniczony zakres liczb typu long .

Podsumowując, przedstawiamy tabela porównawcza czasy wykonania algorytmów o różnej złożoności i wyjaśnić, dlaczego wraz ze wzrostem szybkości komputera znaczenie stosowania szybkich algorytmów znacznie wzrasta.

Rozważ cztery algorytmy rozwiązywania tego samego problemu z odpowiednio złożonością , i . Załóżmy, że drugi z tych algorytmów wymaga dokładnie jednej minuty czasu na wykonanie na jakimś komputerze z wartością parametru. Wtedy czasy wykonania wszystkich tych czterech algorytmów na tym samym komputerze z różnymi wartościami parametru będą w przybliżeniu takie same jak za 10 300000 lat

Gdy początkujący programiści testują swoje programy, wartości parametrów, od których zależą, są zwykle niewielkie. Dlatego nawet jeśli podczas pisania programu zastosowano nieefektywny algorytm, może to pozostać niezauważone. Jeśli jednak podobny program spróbuj zastosować w rzeczywistych warunkach, wtedy natychmiast ujawni się jego praktyczna nieprzydatność.

Wraz ze wzrostem szybkości komputerów wzrastają również wartości parametrów, dla których działanie tego lub innego algorytmu jest zakończone w akceptowalnym czasie. Tym samym wzrasta średnia wartość tej wartości, a co za tym idzie, rośnie wartość stosunku czasów wykonania algorytmów szybkich i wolnych. W jaki sposób szybszy komputer, tym większa względna strata przy użyciu złego algorytmu!

Jeśli istnieje jeden algorytm do rozwiązania problemu, to można wymyślić wiele innych algorytmów do rozwiązania tego samego problemu. Który algorytm jest najlepszy do rozwiązania konkretnego problemu? Jakie kryteria należy zastosować, aby wybrać algorytm z zestawu możliwych? Z reguły dokonujemy oceny algorytmu na podstawie jego oceny przez wykonawcę. Algorytm wydaje nam się skomplikowany, jeśli nawet po dokładnym przestudiowaniu nie możemy zrozumieć, co robi. Algorytm możemy nazwać złożonym i mylącym ze względu na to, że ma on rozgałęzioną strukturę logiczną zawierającą wiele kontroli warunków i przejść. Jednak dla komputera wykonanie programu, który implementuje taki algorytm, nie będzie trudne, ponieważ wykonuje jedno polecenie po drugim i dla komputera nie ma znaczenia, czy jest to operacja mnożenia, czy test warunku.

Co więcej, możemy napisać uciążliwy algorytm, w którym powtarzające się akcje są wypisywane w rzędzie (bez użycia struktury cyklicznej). Jednak z punktu widzenia komputerowej implementacji takiego algorytmu praktycznie nie ma różnicy, czy program używa instrukcji pętli (np. słowo „Hello” jest wyświetlane 10 razy), czy też instrukcji wyświetlania słowa „Cześć” wypisywane jest kolejno 10 razy.

Aby ocenić efektywność algorytmów, pojęcie złożoność algorytmu.

Definicja. proces obliczeniowy, generowana przez algorytm jest sekwencją kroków algorytmu, które przeszły podczas wykonywania tego algorytmu.

Definicja. Złożoność algorytmu to liczba kroków elementarnych w proces obliczeniowy ten algorytm.

Należy pamiętać, że jest to proces obliczeniowy, a nie sam algorytm. Oczywiście, aby porównać złożoność różnych algorytmów, konieczne jest obliczenie złożoności w tych samych elementarnych operacjach.

Definicja. Złożoność czasowa algorytmu to czas T wymagany do jego ukończenia. Jest równy iloczynowi liczby czynności podstawowych przez średni czas wykonania jednej czynności: T = kt.

O ile T zależy od wykonawcy implementującego algorytm, naturalne jest założenie, że złożoność algorytmu zależy przede wszystkim od: k. Oczywiście w największym stopniu liczba operacji w wykonaniu algorytmu zależy od ilości przetwarzanych danych. Rzeczywiście, sortowanie alfabetyczne listy 100 nazwisk zajmuje znacznie mniej operacji niż sortowanie listy 100 000 nazwisk. Dlatego złożoność algorytmu jest wyrażana jako funkcja ilości danych wejściowych.

Niech będzie algorytm A. Dla niego jest parametr a, charakteryzujący ilość danych przetwarzanych przez algorytm często nazywa się ten parametr wymiar zadania. Oznacz przez T(n) czas wykonania algorytmu F- jakaś funkcja z P.

Definicja. Powiemy, że T(n) algorytm ma kolejność wzrostu f(n) lub innymi słowy, algorytm ma złożoność teoretycznaO * (f(n)), jeśli są takie stałe od 1 , od 2> 0 i liczba n 0 , Co c 1 f(n)) < T(p)< c 2 f(n) dla wszystkich n >= n 0 . Tutaj zakłada się, że funkcja f(n) nieujemna, ale przynajmniej n >= n 0 . Jeśli dla T(p) warunek T(n)<= por (n), to mówi się, że algorytm ma złożoność teoretyczna O(p) (odczytaj „o” duże od n).

Czyli na przykład algorytm, który wykonuje tylko operacje odczytu danych i umieszczania ich w pamięci RAM, ma liniowy złożoność 0(n). Algorytm sortowania bezpośredniego ma kwadratowy złożoność 0(p 2) , ponieważ sortując dowolną tablicę, musisz wykonać (p 2 - p) / 2 operacje porównawcze (przy czym może nie być w ogóle żadnych operacji permutacyjnych np. na uporządkowanej tablicy, w najgorszym przypadku konieczne będzie wykonanie P permutacje). I złożoność algorytmu mnożenia matryce(tabele) rozmiar P x P już będzie sześcienny O(n 3) , ponieważ każdy element macierzy wynikowej wymaga P mnożenia i n - 1 dodatki, ale wszystkie te elementy n 2 .

W celu rozwiązania problemu można opracować algorytmy o dowolnej złożoności. Logiczne jest wykorzystanie najlepszych z nich, tj. o najmniejszej złożoności.

Wraz ze złożonością ważną cechą algorytmu jest: efektywność. Efektywność rozumiana jest jako spełnienie następującego warunku: nie tylko cały algorytm, ale także każdy jego krok musi być taki, aby wykonawca był w stanie je wykonać w skończonym, rozsądnym czasie. Na przykład, jeśli algorytm tworzący prognozę pogody na następny dzień będzie wykonywany przez tydzień, to nikt nie potrzebuje takiego algorytmu, nawet jeśli jego złożoność jest minimalna dla klasy podobnych problemów.

Jeśli weźmiemy pod uwagę algorytmy, które są zaimplementowane na komputerze, to wymóg wykonania w rozsądnym czasie jest dodany do wymogu wykonania w ograniczonej ilości pamięć o dostępie swobodnym.

Wiadomo, że w wielu językach programowania nie ma operacji potęgowania, dlatego taki algorytm musi sam programista napisać. Operacja potęgowania jest realizowana przez operacje mnożenia; wraz ze wzrostem wykładnika wzrasta liczba operacji mnożenia, których wykonanie zajmuje dużo czasu. Dlatego istotna jest kwestia stworzenia wydajnego algorytmu potęgowania.

Rozważ metodę szybkiego obliczania naturalnej potęgi liczby rzeczywistej X. Ta metoda została opisana przed naszą erą w starożytnych Indiach.

Zapiszmy P w systemie binarnym.

Zastąpmy każdą „1” w tym wpisie parą liter KH, a każde "O" - litera K.

Usuń skrajną lewą parę kanałów.

Wynikowy ciąg, czytany od lewej do prawej, daje regułę szybkiego obliczania xn, jeśli list DO traktowany jako operacja podniesienia wyniku do kwadratu, a litera x- jako operacja mnożenia wyniku przez X. Początkowo wynikiem jest X.

Przykład 1. Podnieś x do potęgi n = 100.

Przetłumaczmy liczbę n na binarny system liczbowy: n \u003d 100 10 \u003d 1100100,

Budujemy sekwencję KHKKKKKKKK

Przekreśl AX po lewej => KHKKKKKK

Obliczamy pożądaną wartość

K => kwadrat x => otrzymujemy x 2,

X => pomnóż wynik przez x => uzyskaj x 3

K => podnieś wynik do kwadratu => uzyskaj x 6

K => poddajemy wynik do kwadratu => otrzymujemy x 12,

K => podnieś wynik do kwadratu => uzyskaj x 24,

X => pomnóż wynik przez x => uzyskaj x 25

K => podnieś wynik do kwadratu => uzyskaj x 50

K => podnieś wynik do kwadratu => uzyskaj x 100.

W ten sposób obliczyliśmy setną potęgę liczb w zaledwie 8 mnożeniach. Ta metoda jest dość wydajna, ponieważ nie wymaga dodatkowej pamięci RAM do przechowywania wyników pośrednich. Należy jednak pamiętać, że ta metoda nie zawsze jest najszybsza.

Na przykład przy n = 49 uczniowie mogą wymyślić następujący wydajny algorytm potęgowania:

Przy implementacji tego algorytmu wykonano 7 operacji mnożenia (zamiast 48 operacji przy obliczaniu „na czole”) oraz użyto 3 komórek (do przechowywania zmiennej x, aby zapisać wartość x 16 oraz zapisanie aktualnego wyniku uzyskanego na każdym etapie). Jeśli użyjemy algorytmu „Szybkie potęgowanie”, to otrzymamy taką samą liczbę operacji (7 operacji mnożenia), ale do zaimplementowania tego algorytmu (do przechowywania zmiennej) potrzebne są tylko 2 komórki x i zapisać aktualny wynik).

Sama operacja mnożenia realizowana jest w procesorze nie „na czole”, ale znowu poprzez wydajne algorytmy rekurencyjne. Możesz przeczytać o jednym z tych algorytmów w Czytniku. Rozważymy algorytm „szybkiego” mnożenia, który był znany w starożytnym Egipcie, nazywany jest również metodą „rosyjską” lub „chłopską”. Rozważmy przykład zastosowania tego algorytmu.

Przykład 2. Pomnóżmy 23 przez 43 metodą „rosyjską”.

Odpowiedź: 23 x 43 = 23 + 46 + 184 + 736 = 989.

Ostateczna suma obejmuje liczby z pierwszej kolumny, obok których znajdują się liczby nieparzyste w drugiej kolumnie.

O(1) - Większość operacji w programie wykonywana jest tylko raz lub tylko kilka razy. Algorytmy o stałej złożoności. Każdy algorytm, który zawsze wymaga takiej samej ilości czasu, niezależnie od rozmiaru danych, ma stała złożoność.

NA) - Czas trwania programu liniowo zwykle, gdy każdy element danych wejściowych musi zostać przetworzony tylko liniową liczbę razy.

O(N 2), O(N 3), O(N a) - Złożoność wielomianowa.

O(N 2) – złożoność kwadratowa, O(N 3) – złożoność sześcienna

O(Dziennik(N)) - Kiedy program działa czas logarytmiczny, program zaczyna działać znacznie wolniej wraz ze wzrostem N. Taki czas działania zwykle występuje w programach, które dzielą wielki problem na małe i rozwiąż je osobno.

O(N*log(N)) - Taki czas działania mają te algorytmy, które dzielenie dużego problemu na małe, a następnie, po ich rozwiązaniu, połącz ich rozwiązania.

O(2 N) = złożoność wykładnicza. Takie algorytmy najczęściej wynikają z podejścia zwanego brute force.

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 kontrolnych.

Algorytmy bez pętli i wywołania rekurencyjne mają stałą złożoność. Jeśli nie ma rekurencji i pętli, wszystkie struktury kontrolne można zredukować do struktur o stałej złożoności. W konsekwencji cały algorytm charakteryzuje się również stałą złożonością.

Określenie złożoności algorytmu zasadniczo sprowadza się do analizy pętli i wywołań rekurencyjnych.

Rozważmy na przykład algorytm przetwarzania elementów tablicy.
Dla i:=1 do N do
Zaczynać
...
kończyć się;

Złożoność tego algorytmu wynosi O(N), ponieważ treść pętli jest wykonywana N razy, a złożoność ciała pętli wynosi O(1).

Jeżeli jedna pętla jest zagnieżdżona w drugiej i obie pętle zależą od wielkości tej samej zmiennej, to cała konstrukcja charakteryzuje się kwadratową złożonością.
Dla i:=1 do N do
Dla j:=1 do N do
Zaczynać
...
kończyć się;
Złożoność tego programu to O(N 2).

istnieje dwa sposoby analizy złożoności algorytmu: bottom-up (od struktur kontroli wewnętrznej do zewnętrznej) oraz malejąco (z zewnątrz i wewnątrz).

O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(warunki dominujące)=O(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O (N 2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N2)=O(N3);
O(D)=O(A)+O(E)=O(1)+O(N3)=O(N3)

Złożoność ten algorytm O(N3).

Z reguły około 90% czasu wykonywania programu wymaga powtórzeń, a tylko 10% to rzeczywiste obliczenia. Analiza złożoności programów pokazuje, które fragmenty wpadają w te 90% - są to cykle o największej głębokości zagnieżdżenia. Powtórzenia można zorganizować jako zagnieżdżone pętle lub zagnieżdżoną rekurencję.

Te informacje mogą być wykorzystane przez programistę do zbudowania wydajniejszego programu w następujący sposób. Przede wszystkim możesz spróbować zmniejszyć głębokość zagnieżdżenia powtórzeń. Następnie rozważ zmniejszenie liczby instrukcji w najbardziej zagnieżdżonych pętlach. Jeśli 90% czasu wykonania to wykonanie pętli wewnętrznych, to 30% redukcja w tych małych sekcjach skutkuje 90% * 30% = 27% skróceniem czasu wykonania całego programu.

To najprostszy przykład.

Osobny dział matematyki zajmuje się analizą efektywności algorytmów, a znalezienie najbardziej optymalnej funkcji nie jest takie proste.

Oceńmy algorytm wyszukiwania binarnego w tablicy - dychotomia.

Istota algorytmu: przechodzimy na środek tablicy i szukamy zgodności klucza z wartością środkowego elementu. Jeśli nie możemy znaleźć dopasowania, sprawdzamy względny rozmiar klucza i wartość środkowego elementu, a następnie przechodzimy do dolnej lub górnej połowy listy. W tej połowie ponownie szukamy środka i ponownie porównujemy go z kluczem. Jeśli to nie zadziała, ponownie dzielimy bieżący przedział przez połowę.

wyszukiwanie funkcji (niski, wysoki, klucz: liczba całkowita): liczba całkowita;
var
mid, dane: liczba całkowita;
zaczynać
gdy niski<=high do
zaczynać
środek:=(niski+wysoki) dział 2;
dane:=a;
jeśli klucz=dane to
szukaj:=średni
w przeciwnym razie
jeśli klucz< data then
wysoki:=średni-1
w przeciwnym razie
niski:=średni+1;
kończyć się;
szukaj:=-1;
kończyć się;

Pierwsza iteracja pętli zajmuje się całą listą. Każda kolejna iteracja zmniejsza o połowę rozmiar podlisty. Tak więc rozmiary listy dla algorytmu są

n n/2 1 n/2 2 n/2 3 n/2 4 ... n/2 m

W końcu będzie liczba całkowita m taka, że

n/2m<2 или n<2 m+1

Ponieważ m jest pierwszą liczbą całkowitą, dla której n/2 m<2, то должно быть верно

n/2 m-1 >=2 lub 2 m =

Wynika, że
2 m = Bierzemy logarytm każdej części nierówności i otrzymujemy
m= Wartość m jest największą liczbą całkowitą, która =<х.
A więc O(log 2 n).

Zwykle rozwiązywany problem ma naturalny „rozmiar” (zwykle ilość przetwarzanych danych), który nazywamy N. Docelowo chcielibyśmy otrzymać wyrażenie na czas, jaki zajmuje programowi przetworzenie danych o rozmiarze N, jako funkcja N. Zwykle nie interesuje nas przeciętny przypadek - oczekiwany czas działania programu na "typowych" wejściach, a najgorszy przypadek to oczekiwany czas działania programu na najgorszych możliwych wejściach.

Niektóre algorytmy są dobrze rozumiane w tym sensie, że znane są dokładne wzory matematyczne dla przypadków średnich i najgorszych. Takie formuły są opracowywane poprzez dokładne badanie programów w celu znalezienia czasu działania pod względem cech matematycznych, a następnie wykonanie ich matematycznej analizy.

Kilka ważnych powodów takiej analizy to:
1. Programy napisane w języku wysokiego poziomu są tłumaczone na kody maszynowe i może być trudno zrozumieć, ile czasu zajmie wykonanie określonej instrukcji.
2. Wiele programów jest bardzo wrażliwych na dane wejściowe, a ich skuteczność może być od nich bardzo zależna. Przeciętny przypadek może okazać się matematyczną fikcją niezwiązaną z danymi, na których program jest używany, a najgorszy przypadek jest mało prawdopodobny.

Najlepsze, średnie i najgorsze przypadki odgrywają bardzo dużą rolę w sortowaniu.
Ilość obliczeń przy sortowaniu

Analiza O-złożoności stała się szeroko rozpowszechniona w wielu praktycznych zastosowaniach. Jednak jego ograniczenia muszą być jasno zrozumiane.

DO główne wady podejścia może obejmować:
1) dla złożonych algorytmów uzyskanie O-estymacji jest z reguły albo bardzo pracochłonne, albo prawie niemożliwe,
2) często trudno jest określić złożoność „średnio”,
3) Oszacowania O są zbyt zgrubne, aby odzwierciedlić mniejsze różnice między algorytmami,
4) O-analiza dostarcza zbyt mało informacji (lub wcale) do przeanalizowania zachowania algorytmów podczas przetwarzania niewielkich ilości danych.

Określenie złożoności w notacji O nie jest zadaniem trywialnym. W szczególności o skuteczności wyszukiwania binarnego decyduje nie głębokość zagnieżdżenia pętli, ale sposób doboru każdej kolejnej próby.

Kolejną trudnością jest definicja „średniego przypadku”. Zwykle jest to dość trudne ze względu na niemożność przewidzenia warunków pracy algorytmu. Czasami algorytm jest używany jako fragment dużego, złożonego programu. Czasem wydajność sprzętu i/lub systemu operacyjnego lub jakiegoś elementu kompilatora znacząco wpływa na złożoność algorytmu. Często ten sam algorytm może być używany w wielu różnych aplikacjach.

Ze względu na trudności związane z analizą złożoności czasowej algorytmu „średnio”, często trzeba zadowolić się szacunkami dla najgorszych i najlepszych przypadków. Te wyniki zasadniczo określają dolne i górne granice „przeciętnej” złożoności. Właściwie, jeśli nie można przeanalizować złożoności algorytmu „średnio”, pozostaje przestrzegać jednego z praw Murphy'ego, zgodnie z którym oszacowanie uzyskane dla najgorszego przypadku może służyć jako dobre przybliżenie złożoności „średnio”. ”.

Być może główną wadą funkcji O jest ich nadmierna chropowatość. Jeśli algorytm A wykona jakieś zadanie w 0,001*N s, a algorytm B potrzebuje 1000*N s na jego rozwiązanie, to B jest milion razy szybszy niż A. Niemniej jednak A i B mają tę samą złożoność czasową O(N).

Większość tego wykładu była poświęcona analizie złożoności czasowej algorytmów. Istnieją inne formy złożoności, o których nie należy zapominać: złożoność przestrzenna i intelektualna.

Złożoność przestrzeni jako ilość pamięci wymaganej do wykonania programu została już wspomniana wcześniej.

Analizując złożoność intelektualną algorytmu, bada się zrozumiałość algorytmów i złożoność ich rozwoju.

Wszystkie trzy formy złożoności są zwykle ze sobą powiązane. Z reguły przy tworzeniu algorytmu o dobrej ocenie złożoności czasowej należy poświęcić jego złożoność przestrzenną i/lub intelektualną. Na przykład algorytm szybkiego sortowania jest znacznie szybszy niż algorytm sortowania przez wybór. Opłatą za większą prędkość sortowania jest większa ilość pamięci potrzebnej do sortowania. Potrzeba dodatkowej pamięci do szybkiego sortowania wynika z wielu wywołań rekurencyjnych.

Algorytm szybkiego sortowania charakteryzuje się również większą złożonością intelektualną w porównaniu z algorytmem sortowania przez wstawianie. Jeśli poprosisz setki osób o posortowanie sekwencji obiektów, prawdopodobnie większość z nich użyje algorytmu sortowania przez wybór. Jest też mało prawdopodobne, że którykolwiek z nich użyje szybkiego sortowania. Przyczyny większej złożoności intelektualnej i przestrzennej sortowania szybkiego są oczywiste: algorytm jest rekurencyjny, raczej trudno go opisać, algorytm jest dłuższy (czyli tekst programu) niż prostsze algorytmy sortowania.

Hej! Dzisiejszy wykład będzie trochę inny od reszty. Będzie się różnił tym, że jest tylko pośrednio związany z Javą. Jednak ten temat jest bardzo ważny dla każdego programisty. Porozmawiamy o algorytmy. Czym jest algorytm? Mówiąc prościej, jest to sekwencja działań, które należy wykonać, aby osiągnąć pożądany rezultat. Często używamy algorytmów w naszym codziennym życiu. Na przykład każdego ranka masz zadanie: przyjść do szkoły lub pracy, a jednocześnie być:

• Ubrany
• czysty
• pełny

1. Obudź się z alarmem.
2. Weź prysznic, umyj się.
3. Przygotuj śniadanie, zrób kawę/herbatę.
4. Jeść.
5. Jeśli nie prasowałeś ubrań od wieczora, wyprasuj je.
6. Ubrać się.
7. Opuścić dom.

1. Kup lub pobierz w Internecie „Słownik rosyjskich imion osobistych” wydanie 1966.
2. Znajdź każde imię z naszej listy w tym słowniku.
3. Zapisz na kartce, na której stronie słownika znajduje się nazwa.
4. Uporządkuj nazwy za pomocą notatek na kartce papieru.

Złożoność logarytmiczna