ASD - ukochane

Algorytm poprawny częściowo - (dla dowolnych danych wejściowych i dowolnych danych wyjściowych) - jeśli się zatrzymuje dla danych spełniających warunek początkowy, to wyniki spełniają warunek końcowy.

Algorytm poprawny - (dla dowolnych danych wejściowych i dowolnych danych wyjściowych) - zawsze się zatrzymuje dla danych spełniających warunek początkowy i wyniki spełniają warunek końcowy.

Złożoność obliczeniowa algorytmu to złożoność czasowa i pamięciowa.

Operacja elementarna (inaczej operacja dominująca) to operacja charakterystyczna dla danego algorytmu. To taka operacja, że łączna ich liczba jest proporcjonalna do liczby wykonań wszystkich operacji jednostkowych w dowolnej komputerowej realizacji algorytmu.

Za jednostkę złożoności czasowej przyjmuje się wykonanie jednej operacji elementarnej (dominującej). Złożoność czasowa algorytmu jest funkcją rozmiaru danych.

Mówimy, że f jest co najwyżej rzędu g, co zapisujemy f(n)=O(g(n))

Mówimy, że f jest co najmniej rzędu g, co zapisujemy f(n)=Ω(g(n))

Mówimy, że f jest dokładnie rzędu g, co zapisujemy f(n)=Θ(g(n))

! Aby zastosować strategię dziel i zwyciężaj należy mieć ciąg posortowany niemalejąco.

Wyszukiwanie elementu w wektorze:

Przy zastosowaniu standardu koszt jest liniowy, a dane „najgorszego” przypadku to ciąg, w którym x (szukany element) nie występuje i wszystkie liczby w ciągu są mniejsze od x.

Przy zastosowaniu dziel i zwyciężaj mamy koszt
a przypadek pesymistyczny to nie wystąpienie x.

Wyszukiwanie min i max:

Standard: Koszt jest liniowy 2(n-1), a przypadkiem pesymistycznym jest ustawienie elementów malejąco.

Dziel i zwyciężaj: Koszt jest liniowy
, a przypadek pesymistyczny spełniają dowolne dane spełniające warunek początkowy.

Sprawdzanie czy punkt należy do wielokąta wypukłego:

Naiwny: Koszt jest n^3 (można go obniżyć do n jeśli będzie dobierało się trójkąty o wspólnym wierzchołku n-1).

Dziel i zwyciężaj: Koszt

Rekord wywołania (aktywacji) zawiera:

-wartości wszystkich parametrów funkcji,

-zmienne lokalne funkcji

-adres powrotu - adres instrukcji w kodzie programu, następującej bezpośrednio po

wywołaniu funkcji

-dynamiczne dowiązanie - wskaźnik na poprzedni rekord aktywacji

-zwracana wartość funkcji

Rodzaje rekurencji:

1.Rekursja końcowa

Zawiera tylko jedno wywołanie rekurencyjne na końcu funkcji. Taki rodzaj rekursji jest po prostu innym zapisem pętli i może być łatwo zastąpiony pętlą.

2.Rekursja niekońcowa

Zawiera jedno wywołanie rekurencyjne, które nie jest ostatnim rozkazem funkcji. Iteracyjna wersja takiej funkcji wymaga zazwyczaj jawnego użycia stosu.

3.Rekursja pośrednia

Przykład: funkcja f wywołuje funkcję g, a g wywołuje funkcję f

4.Rekursja zagnieżdżona

Kiedy funkcja jest zdefiniowana nie tylko za pomocą samej siebie, ale także jest użyta jako jeden z parametrów. Przykładem jest funkcja Ackermana (funkcja Ackermanna rośnie bardzo, bardzo szybko i nie daje się zapisać wzorem, w którym można użyć operacji arytmetycznych, takich jak dodawanie, mnożenie i potęgowanie).

Programowanie dynamiczne

Użycie strategii programowania dynamicznego polega na zapamiętaniu w odpowiedniej strukturze (najczęściej tablicy) wyników rozwiązania podproblemów, na które został podzielony problem zasadniczy, unikając w ten sposób wielokrotnych obliczeń dla tego samego podproblemu. Programowanie dynamiczne prowadzi do całkowitej bądź częściowej eliminacji rekurencji.

Obliczanie dwumianu Newtona przy pomocy trójkąta Pascala: koszt O(2^n-m).

Stosując programowanie dynamiczne uzyskujemy koszt

Optymalne mnożenie macierzy:

Naiwny: Sprawdzamy wszystkie możliwości; koszt:

Dynamicznie: Pesymistycznie koszt wynosi
.

Dla problemu triangulacji wielokąta można wykorzystać powyższy algorytm (koszty identyczne).

Sortowanie przez scalanie:

Składa się z dwóch procedur: procedura Merge, gdy każdy z ciągów scalanych ma długość k i wynosi 2k-1 zaś Merge_Sort
, czyli ogólnie jest log.

Sortowanie przez kopcowanie

Aby mogło zajść muszą być spełnione 2 warunki:

&

Fazy sortowania przez kopcowanie:

I Faza: budowa kopca (procedura down_heap i construct)

II Faza: zamiana elementu pierwszego z ostatnim (procedura delete_max)

III Faza: przywracanie struktury kopca (znowu down_heap w delete_max)

l-poziom

Procedura downheap wywołana dla węzła i z poziomu l wykonuje co najwyżej
porównań. Koszt construct jest liniowy (n). Delete_max ma koszt
. Ogólnie cała procedura Heap_Sort ma kosz
. Nie jest znana pełna analiza średniej złożoności czasowej sortowania przez kopcowanie.Wyniki przeprowadzonych eksperymentów wskazują, że współczynnik przy nlogn jest bliski 2.

Sortowanie szybkie (QuickSort)

Czas działania algorytmu Quick_Sort zależy od tego, czy podziały są zrównoważone, czy nie. Jeżeli podziały są zrównoważone, to algorytm jest asymptotycznie tak szybki jak sortowanie przez scalanie. Kiedy podziały są

niezrównoważone, to algorytm może działać asymptotycznie tak wolno jak sortowanie przez wstawianie.

Najgorszy przypadek podziałów:

Zachodzi wtedy, gdy funkcja Partition zwraca taki indeks podziału, że jeden z obszarów ma n-1 elementów, a drugi zawiera tylko 1 element. Jeżeli taka sytuacja zachodzi w każdym kroku algorytmu, to liczba wykonywanych porównań jest największa.

Jeżeli elementem dzielącym jest pierwszy element sortowanego ciągu, to najgorszy przypadek podziałów zachodzi dla ciągu uporządkowanego. (Koszt n^2).

Najlepszy przypadek podziałów:

Ma miejsce wtedy, gdy funkcja dzieląca Partition „produkuje” dwa obszary o rozmiarach n/2. (Koszt
).

Stos wykorzystywany jest w algorytmie przeglądania grafu „w głąb”, kolejka „wszerz” oraz sito Eratostenesa. Listę można posortować kosztem O(nlogn).

Drzewo BST

Drzewo BST (Binary Search Tree) jest drzewem binarnym z ustalonym porządkiem symetrycznym. Porządek symetryczny polega na tym, że dla każdego węzła x drzewa jest spełniony następujący warunek:

Jeżeli y leży w lewym poddrzewie x, to key(y) ≤ key(x).

Jeżeli y leży w prawym poddrzewie x, to key(x) ≤ key(y).

Relacja ≤ jest relacją porządku liniowego, a key(x) - jest wartością pola (klucza) danych, na którym relacja ≤ jest określona.

Search, Insert mają koszty liniowe. Każdy element dodany do BST jest liściem.

Wysokość drzewa AVL o n wierzchołkach (n≥1) jest nie większa niż 2log₂n.

Operacje słownikowe na drzewie AVL

search(e, d) - operacja realizowana tak samo jak dla drzewa BST

insert(e, d) - operacja realizowana w pierwszej fazie tak samo jak dla drzewa BST, tj. nowy element jest wstawiany jako liść w odpowiednim miejscu w drzewie. Druga faza to

ewentualne wyważenie powstałego drzewa.

delete(e, d) - operacja realizowana w pierwszej fazie tak samo jak dla drzewa BST, tj. w miejsce usuwanego elementu wstawiany jest największy element w lewym poddrzewie usuwanego elementu albo najmniejszy element w jego prawym poddrzewie. Druga faza to ewentualne wyważenie powstałego drzewa.

Rotacje w procesie wyważania wykonywane są tylko na jednej ścieżce w drzewie.

Operacja delete realizowana na drzewie AVL wymaga wykonania co najwyżej 2log₂n rotacji.

Operacja insert realizowana na drzewie AVL wymaga wykonania co najwyżej jednej rotacji.

Operacje słownikowe zrealizowane na drzewie AVL mają koszt pesymistyczny O(logn).

Analiza kosztów haszowania metodą łańcuchową

Niech α oznacza współczynnik zapełnienia tablicy haszującej:
, gdzie n to aktualna liczba danych w słowniku, a m to rozmiar tablicy haszującej. Wartość współczynnika α to średnia długość listy (łańcucha).

W przypadku pesymistycznym wszystkie operacje słownikowe mają złożoność Θ(n), zakładając, że koszt obliczania wartości funkcji haszującej dla danego elementu jest Θ(1).

Przy określaniu złożoności średniej przyjmuje się, że losowo wybrany element z jednakowym prawdopodobieństwem trafia na każdą z m pozycji, niezależnie od tego gdzie trafiają inne elementy. Jeżeli spełnione jest to założenie, to mówimy o prostym równomiernym haszowaniu.

Można pokazać, że:

Twierdzenie

W tablicy z haszowaniem wykorzystującym łańcuchową metodę rozwiązywania problemu kolizji, przy założeniu, o prostym równomiernym haszowaniu, średni czas działania operacji search wynosi Θ(1+α).

Wniosek:

Średni czas realizacji operacji insert i delete wynosi Θ(1+α).

Adresowanie otwarte

Wszystkie elementy słownika są przechowywane wprost w tablicy. Wyszukiwanie elementu polega na systematycznym sprawdzaniu pozycji w tablicy, aż zostanie znaleziony szukany element albo wiadomo już, że na pewno nie ma go w tablicy. Nie ma żadnych dodatkowych list. Przy stosowaniu haszowania otwartego współczynnik zapełnienia α nie może większy od 1, aby nie nastąpiło przepełnienie tablicy.

Operacja delete realizowana metodą haszowania otwartego jest dość skomplikowana i kosztowna czasowo (koszt nie zależy od współczynnika zapełnienia tablicy).

Adresowanie liniowe

Poważną wadą adresowania liniowego jest tendencja do grupowania się zajętych pozycji. długie spójnie wypełnione ciągi zajętych pozycji szybko się powiększają, co znacznie spowalnia operację wyszukiwania.

Adresowanie kwadratowe

Stosujemy tu funkcję postaci:
gdzie
jest zwykłą jednoargumentową funkcją haszującą,
i
są stałymi, a
.

Dla danej e jej ciąg kontrolny zaczyna się od pozycji
. Następna pozycja w tym ciągu jest oddalona od pierwszej o wielkość zależną od kwadratu numeru pozycji i w ciągu kontrolnym. Dobór stałych
i
w decydujący sposób może wpłynąć na efektywność operacji insert i search realizowanych metodą adresowania kwadratowego.

Zauważmy, że jeżeli dwa elementy mają w takie same początkowe pozycje, to i całe ich ciągi kontrolne są równe, ponieważ z
wynika, że
. Prowadzi to do tzw. grupowania wtórnego. Początkowa pozycja określa jednoznacznie, podobnie jak w adresowaniu liniowym, cały ciąg kontrolny.

Haszowanie dwukrotne

Haszowanie dwukrotne dopuszcza użycie Θ(m²) różnych ciągów kontrolnych, a nie tylko Θ(m) ciągów jak w haszowaniu liniowym i kwadratowym. Każda para
wyznacza inny ciąg kontrolny, a dla różnych elementów wartości
i
zmieniają się niezależnie. Dzięki temu haszowanie dwukrotne bardzo dobrze przybliża "idealne" warunki haszowania równomiernego.

Koszt operacji insert i search w adresowaniu otwartym

Jeżeli współczynnik zapełnienia tablicy z haszowaniem
, to średnia liczba porównań wykonanych w czasie realizacji operacji search i insert metodą adresowania otwartego jest nie większa niż
, o ile jest spełnione założenie o równomiernym haszowaniu.

Przeglądanie grafu „wszerz”

Jako operację elementarną przyjmujemy wykonanie operacji in lub out na kolejce Q oraz operację przeglądania list incydencji grafu. Każdy wierzchołek jest wstawiany co najwyżej raz i co najwyżej raz jest z niej usuwany. Stąd łączny czas wykonania operacji na kolejce wynosi O(n). Ponieważ lista incydencji każdego wierzchołka jest przeglądana tylko wtedy, gdy wierzchołek zostanie usunięty z kolejki, lista incydencji każdego wierzchołka jest przeglądana co najwyżej raz. Suma długości wszystkich list wynosi Θ(m). Łączny czas przeglądania list wynosi zatem O(m). Inicjowanie grafu zabiera czas O(n).Koszt BFS wynosi O(m+n).

Przeglądanie grafu w „głąb”

Jako operację elementarną przyjmujemy liczbę wywołań rekurencyjnych procedury DFS_VISIT (operacje stosowe realizowane w stosie wywołań) oraz operację przeglądania list incydencji grafu. Koszt procedury DFS wynosi O(m+n) - uzasadnienie analogiczne jak dla BFS.

Algorytmy zachłanne

Dwie cechy charakterystyczne:

Własność wyboru zachłannego

Jeżeli wybory "lokalne" są optymalne, to wybór "globalny" (ostateczny)

jest optymalny. Różnica między strategią zachłanną a programowaniem dynamicznym polega na tym, że w programowaniu dynamicznym w każdym kroku podejmowane są decyzje, których wybór zależy od rozwiązań podproblemów. W algorytmie zachłannym wybory są podejmowane jako najlepsze (z punktu widzenia zadania) w danej chwili. Wybory podejmowane w algorytmie zachłannym nie są zależne od wyborów przeszłych, w przeciwieństwie do wyborów podejmowanych przy strategii programowania dynamicznego. Można formalnie udowodnić (stosując metodę indukcji), że dany problem ma własność wyboru zachłannego.

Własność optymalnej podstruktury

Problem ma własność optymalnej podstruktury, jeżeli optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. Ta własność jest również spełniona dla problemów rozwiązywalnych metodą programowania dynamicznego.

Dyskretny problem plecakowy nie ma własności wyboru zachłannego. Dyskretny problem plecakowy ma własność optymalnej podstruktury. Ciągły problem plecakowy ma własności wyboru zachłannego. Ciągły problem plecakowy ma własność optymalnej podstruktury.

Koszt złodzieja z plecakiem (ciągły) wynosi: Θ(nlogn). Kruskal i Huffman też wykorzystują algorytm zachłanny. Problem planu zajęć wykona się kosztem liniowym o ile dane sa uporządkowane rosnąco względem czasów zakończenia zajęć.

Złożoność czasowa algorytmu Kruskala

Rozmiar zadania: n - liczba wierzchołków grafu,

m - liczba krawędzi grafu

Koszt operacji MAKE_SETS: O(n)

Koszt utworzenia posortowanej listy krawędzi L: O(nlogn)

Koszt operacji FIND_SET zrealizowanych w pętli (*): O(m)

Koszt operacji UNION zrealizowanych w pętli (*): O(nlogn)

Uwaga ! Koszt pojedynczej operacji UNION, w przypadku pesymistycznym jest O(n), ale koszt n-1 operacji UNION w pętli (*) jest O(nlogn), a nie O(n²). Liczymy bowiem, ile razy dany element może mieć zmieniane dowiązanie do głowy listy. Za każdym razem element przechodzi do listy o rozmiarze co najmniej dwukrotnie większym. Zmian takich może być co najwyżej logn.

Wniosek

Złożoność czasowa algorytmu Kruskala zrealizowanego w strukturze

listowej jest O(m + nlogn)

Algorytm Huffmana

długość ciągu wejściowego - długość ciągu wyjściowego

długość ciągu wejściowego

To jest najlepszy współczynnik kompresji - mniejszego już nie można uzyskać.

Aby kompresja była poprawna muszą być spełnione następujące warunki:

-Każdy kod odpowiada dokładnie jednemu symbolowi.

-Dekodowanie nie powinno wymagać podglądania większego fragmentu zakodowanego tekstu. Po wczytaniu z pliku pojedynczego symbolu powinniśmy umieć stwierdzić, czy osiągnięty został koniec napisu kodującego symbol pierwotnej wiadomości. Nie są więc potrzebne żadne specjalne znaki oddzielające dwa kody w sąsiedniej wiadomości.

Koszt czasowy algorytmu kompresji:

Rozmiar zadania: n - rozmiar alfabetu

m - liczba znaków pliku, który kompresujemy

1. Tworzenie uporządkowanej listy jednowęzłowych drzew

kosztuje optymalnie Θ(nlogn).

2. Jeden krok procesu scalania dwóch węzłów drzewa Huffmana jest realizowany kosztem stałym Θ(1). Cały proces tworzenia drzewa Huffmana kosztuje zatem Θ(n).

3. Proces ustalania wszystkich kodów kompresji kosztuje Θ(n).

Można go zrealizować stosując metodę przeglądania drzewa

binarnego w porządku inorder (poprzeczny: L - K- P).

4. Krok algorytmu kompresji, który ustala kody znaków wpisywanych do skompresowanego pliku ma również koszt rzędu Θ(m).

Stąd wynika, że koszt algorytmu kompresji metodą Huffmana pliku zawierającego m znaków nad n elementowym alfabetem wynosi Θ(nlogn+m).

Sortowanie przez zliczanie

Koszt inicjalizacji tablicy C: k

Koszt I kroku: n

Koszt II kroku: k-1

Koszt III kroku: 2n

Koszt łączny: 2k + 3n - 1=O(n+k)

Sortowanie pozycyjne

Złożoność czasowa : Zależy od metody sortowania jaką zastosuje my w pojedynczym kroku tj. po danej cyfrze. Musi być to metoda stabilna. Jeżeli każda z cyfr należy do przedziały od 1 do k oraz k nie jest zbyt duże, to należy użyć sortowania przez zliczanie. Każdy przebieg przez n cyfr d- cyfrowych liczb wymaga czasu Θ(n+k). Ponieważ algorytm wykonuje d przebiegów, więc całkowity czas działania sortowania pozycyjnego wynosi Θ(dn+dk). Jeśli d jest stałą, a k=O(n), to sortowanie pozycyjne działa w czasie liniowym.

Sortowanie kubełkowe

Złożoność czasowa:

Koszt pierwszej pętli wynosi O(n).

Koszt operacji łączenia list B[i] jest również O(n).

Koszt drugiej pętli zależy od długości list B[i].

Niech n_i oznacza liczbę elementów w kubełku B[i].

Sortowanie przez wstawianie ma koszt pesymistyczny O(n²) dla ciągu

długości n.

Można pokazać, że koszt średni drugiej pętli wynosi O(n).

Sortowanie kubełkowe ma pesymistyczny koszt O(n² ), a średni O(n).

Wyszukiwanie wzorca w tekście

Koszt czasowy algorytmu naiwnego

Operacją elementarną są porównania między znakami wzorca

i tekstu. Jeśli wzorzec nie występuje w tekście i przekonujemy się o tym po pierwszym porównaniu (przy każdym położeniu wzorca względem tekstu), to wykonujemy minimalną liczbę porównań równą n-m+1. Jeżeli wzorzec występuje na każdej pozycji tekstu, na przykład, gdy:

T: aⁿ, P: a^m,

to wykonujemy maksymalną liczbę porównań równą :

(n - m+1)⋅ m.

Zatem:

Można pokazać, że koszt średni algorytmu naiwnego jest O(n-m+1).

Koszt czasowy algorytmu KMP

Koszt obliczenia wszystkich wartości funkcji  wynosi O(m), gdyż :

(1) warunek P[k+1] =P[q] (po pętli) może być sprawdzany co

najwyżej m razy, a z drugiej strony,

(2) warunek P[k+1]<>P[q] (w pęli) też może być sprawdzany

co najwyżej m razy.

Stąd, razem mamy co najwyżej 2m porównań.

Można uzasadnić, że koszt średni zasadniczego algorytmu KMP jest O(n).

Można pokazać, że całkowity koszt średni algorytmu KMP wynosi O(n+m).

Koszt czasowy algorytmu RK

Operacją elementarną nie są tym razem porównania między znakami wzorca i tekstu, a operacje arytmetyczne realizowane przy obliczaniu odcisku wzorca i tekstu.

Odcisk wzorca można policzyć kosztem O(m). Odcisk t₀ również można obliczyć takim samym kosztem. Odciski t₁,...,t_n-m można policzyć stałym kosztem, gdy mamy wcześniej policzoną jednorazowo wartość 10 ^m-1 (można tę wartość policzyć kosztem O(logm), stosując algorytm oparty na metodzie "dziel i zwyciężaj". Zatem koszt całego algorytmu wyniesie O(n+m).

Problem 1

Wartości p i t₀, t₁,..., t_n-m mogą być bardzo duże, a wtedy trudno uważać że każda operacja arytmetyczna ma ten sam koszt.

Rozwiązanie Problemu 1

Problem ten można rozwiązać stosując zamiast zwykłej arytmetyki, arytmetykę modulo.

Obliczone wartość odcisku dzieli się modulo pewna wybrana

liczba pierwsza q.

Zwykle wybiera się q takie, że d⋅q ( w naszych przykładach d = 10) powinno być nie większe niż jedno słowo maszynowe.

Obliczanie następnego ''odcisku palca'' dla tekstu wygląda następująco:

t_s+1 =(d⋅(t_s - d ^m-1⋅T[s+1])+T[s+m+1]) mod q

Problem 2

Pojawia się jednak problem jednoznaczności:

Prawdziwość warunku t _s = p mod q nie oznacza, że na pewno

P[1...m]=T[s+1 ... s+m]

Aby algorytm nie zwracał niepoprawnych wyników należy w każdym przypadku gdy t_s = p mod q dodatkowo sprawdzić równość odpowiednich ciągów badając je znak po znaku.
Powoduje to jednak, że koszt algorytmu RK, w najgorszym przypadku wynosi Θ((n-m+1) ⋅m).

Przykładem przypadku pesymistycznego dla algorytmu RK jest przypadek: T = aⁿ i P = a^m. Wówczas każdy blok tekstu o długości m daje ten sam odcisk równy odciskowi wzorca i konieczne jest sprawdzenie znak po znaku.

W bardzo wielu zastosowaniach , zajście zdarzenia

t_s = p mod q,

przy jednoczesnej niezgodności wzorca z tekstem, jest bardzo rzadkie. Liczbę q można tak wybrać aby prawdopodobieństwo, że t_s = p mod q było równe 1/n. Wtedy czas oczekiwany wykonania algorytmu RK wynosi O(n+m).

Wersja bez sprawdzania symbol po symbolu i z arytmetyką modulo q gwarantuje zaś liniowy czas wykonania, ale z małym prawdopodobieństwem wynik może się okazać niepoprawny. Takie algorytmy, które z dopuszczalnym prawdopodobieństwem zwracają wynik niepoprawny nazywamy algorytmami MonteCarlo (zawsze szybko i prawdopodobnie poprawnie). Wersja algorytmu ze sprawdzaniem w przypadku, gdy odcisk wzorca jest zgodny mod q z odciskiem bloku tekstu gwarantuje poprawny wynik, ale z małym prawdopodobieństwem algorytm ten będzie działał dłużej niż liniowo (metoda LasVegas - zawsze poprawnie i prawdopodobnie szybko).

Geometria obliczeniowa

Koszt sprawdzania czy punkt należy do dowolnego wielokąta jest liniowy.

Koszt czasowy algorytmu naiwnego

Rozmiar zadania:
- liczba punktów zbioru S.

Operacja elementarna:

• operacja sprawdzania, czy punkt należy do trójkąta

(odcinka) w Kroku 1,

• operacja porównania wykonana w trakcie sortowania

w Kroku 2.

Koszt czasowy Kroku 1: Dla n punktów trzeba sprawdzić co najwyżej
różnych trójkątów. Stąd koszt Kroku 1 jest O(n⁴).

Koszt czasowy Kroku 2: Jeżeli zastosujemy optymalną metodę sortowania to koszt czasowy Kroku 2 jest O(nlogn).Całkowity koszt czasowy algorytmu naiwnego jest więc rzędu

O(n⁴). Efektywne algorytmy rozwiązujące problem otoczki wypukłej, algorytm Grahama i Jarvisa, mają zasadniczo niższy koszt.

Koszt czasowy algorytmu Grahama

Na złożoność algorytmu Grahama decydujący wpływ ma Krok 2. Kroki 1 i 2 wykonywane są w czasie liniowym.

Krok 2 można zrealizowany w czasie O(nlogn), stosując efektywną metodę sortowania (np. sortowanie przez scalanie,

sortowanie przez połówkowe wstawianie czy sortowanie szybkie).

Łatwo zauważyć, że zamiast sprawdzać, czy punkt next(q) leży wewnątrz trójkąta O q next(next(q)) można testować, czy next(q) leży po lewej stronie (lub należy do) wektora
. Złożoność algorytmu Grahama nie zależy od liczby punktów otoczki wypukłej. Następny algorytm rozwiązujący problem otoczki, algorytm Jarvisa, ma złożoność O(kn), gdzie k jest liczbą punktów otoczki wypukłej w danym n elementowym zbiorze punktów.

Złożoność czasowa algorytmu Jarvisa

Każda iteracja w Krokach 2 i 3 jest wykonywana w czasie O(n). Ponieważ liczba iteracji jest równa liczbie wierzchołków otoczki, to koszt całkowity algorytmu Jarvisa wynosi O(kn).

Algorytm ten jest szczególnie przydatny wtedy, gdy wiemy, że liczba punktów otoczki wypukłej jest niewielka w porównaniu z rozmiarem zbioru S (na przykład ograniczona przez stałą niezależną od n).

Algorytm znajdowania najmniej odległych punktów

Koszt czasowy algorytmu naiwnego

Liczba par punktów do sprawdzenia wynosi
. Stąd koszt

algorytmu jest

Koszt czasowy algorytmu znajdywania najmniej odległej pary punktów

Koszt sortowania wstępnego (przed pierwszym wywołaniem rekurencyjnym) tablic X i Y wynosi Θ(nlogn). Dzięki temu, że tablica X jest posortowana, krok polegający na rozdzieleniu zbioru punktów P na podzbiory P_L i P_R można łatwo zrealizować w czasie liniowym. Dzięki temu, że tablica Y jest posortowana, stałą liczbą porównań można zrealizować krok

polegający na sprawdzeniu, czy istnieją dwa punkty, leżące po przeciwnych stronach prostej l, których odległość jest mniejsza od
.

Posortowane tablice zostają przekazane jako parametry pierwszego wywołania rekurencyjnego, a potem rozdziela się je (pod warunkiem, że zawierają co najmniej trzy punkty) na dwie, również posortowane tablice: z tablicy X otrzymujemy tablice X_L i X_R , a tablicy Y otrzymujemy tablice Y_L i Y_R . Wszystkie cztery tablice również muszą być posortowane. Aby uniknąć ponownego sortowania całych tablic, podczas rozdzielania tablic X i Y stosujemy technikę podobną, ale odwrotną do procedury MERGE (scalania) w algorytmie sortowania MergeSort.

Algorytm zamiatania

Algorytm naiwny

Sprawdzamy wszystkie możliwe pary odcinków. Koszt algorytmu naiwnego jest równy

Koszt czasowy algorytmu sprawdzania przecinania się odcinków

Jeśli S zawiera n odcinków, to algorytm działa w czasie O(nlogn). Czas tworzenia posortowanej listy L może optymalnie wynieść O(nlogn). Pętla wykonuje co najwyżej 2n kroków, bo tyle co najwyżej zdarzeń może zajść dla n odcinków. Każdy krok pętli realizuje się w czasie O(logn), pod warunkiem, że struktura stanu miotły jest realizowana optymalnie.

Problemy łatwo rozwiązalne to takie, dla których można podać algorytm o wielomianowej złożoności czasowej, czyli taki, którego koszt jest O(n^k) (dla pewnego k).

Problemy o złożoności wyższej niż wielomianowa, czyli takiej, że nie da się jej ograniczyć przez O(n^k), dla dowolnego k, nazywamy trudno rozwiązalnymi.

Złożoność algorytmu rozwiązującego problem wież Hanoi

Można wykazać, że nie istnieje algorytm rozwiązujący problem wież Hanoi o złożoności niższej niż Θ(2ⁿ).

Algorytm znalezienia cyklu Hamiltona

Koszt algorytmu naiwnego to

Złożoność czasowa algorytmu generowania cykli Hamiltona (strategia powrotów)

Drzewo możliwych "rozszerzeń" rozwiązania częściowego jest drzewem wielokierunkowym o wysokości równej co najwyżej n. Jeżeli za operację elementarną przyjmiemy każde wywołanie rekurencyjne procedury Hamilton, to koszt algorytmu jest równy liczbie węzłów w drzewie. Można pokazać, że liczba ta jest O(2ⁿ).

Problem ustawienia Hetmanów

Przykłady problemów klasy NP.

-Generowanie cyklu Hamiltona w spójnym grafie

-Problemy ułożeń dwuwymiarowych (czy z wielokątów da się ułożyć prostokąt)

-Problem komiwojażera

-Problem ułożenia planu

-Ustalanie prawdy logicznej (problem spełnialności)

-Kolorowanie map i grafów

-Problem kliki

-Sprawiedliwy podział

-Szeregowanie zadań niezależnych

-Izomorfizm z podgrafem

Przykłady problemów klasy NP.-zupełnych

Wszystkie wyżej wymienione się do nich zaliczają.

Mówimy, że problem decyzyjny A jest przekształcalny w problem decyzyjny B, jeśli istnieje przekształcenie f :A→B o następujących własnościach:

• odpowiedzi do problemów A i B są zgodne, wartość f(A) można obliczyć w czasie wielomianowo zależnym od rozmiaru zadania A.

Jeżeli problem A jest przekształcalny w problem B oraz A jest problemem klasy NP, to także problem B jest problemem klasy NP.

Jeżeli problem A jest NP - zupełny i jest przekształcalny w problem B oraz B jest problem klasy NP, to B jest NP - zupełny.

Hipoteza P≠NP.

Następujące warunki są równoważne:

Istnieje problem NP- zupełny, który jest trudno rozwiązalny.

Każdy problem NP - zupełny jest trudno rozwiązalny.

Jeżeli ta hipoteza jest prawdziwa, to nie warto szukać rozsądnych rozwiązań dla problemów NP - zupełnych, bo ich po prostu nie ma.

Hipoteza P=NP.

Następujące warunki są równoważne:

Istnieje problem NP- zupełny, który jest łatwo rozwiązalny (należy do klasy P).

Każdy problem NP - zupełny może być rozwiązany w czasie wielomianowym.

Jeżeli ta hipoteza jest prawdziwa, to jeżeli uda się podać rozwiązanie wielomianowe jednego problemu NP- zupełnego, to tym samym rozwiązalne wielomianowo będą pozostałe problemy z tej klasy.

Algorytm umożliwiający otrzymanie prawie optymalnego rozwiązania jest nazywany algorytmem aproksymacyjnym (przybliżonym).

Złożoność czasowa algorytmu przybliżonego (komiwojażer)

Przy jednym uruchomieniu : O(n²).

Przy n uruchomieniach: O(n³)

---