Notacje asymptotyczne i analiza apiori

Przy projektowaniu algorytmu analiza złożoności algorytmu jest istotnym aspektem. Głównie złożoność algorytmiczna dotyczy jego wydajności, szybkości lub wolnej pracy.

Złożoność algorytmu opisuje wydajność algorytmu pod względem ilości pamięci wymaganej do przetwarzania danych i czasu przetwarzania.

Złożoność algorytmu jest analizowana w dwóch perspektywach: Time i Space.

Złożoność czasowa

Jest to funkcja opisująca ilość czasu potrzebnego do uruchomienia algorytmu pod względem wielkości danych wejściowych. „Czas” może oznaczać liczbę wykonanych dostępów do pamięci, liczbę porównań między liczbami całkowitymi, liczbę wykonań jakiejś pętli wewnętrznej lub inną naturalną jednostkę związaną z czasem rzeczywistym, jaki zajmie algorytm.

Złożoność przestrzeni

Jest to funkcja opisująca ilość pamięci, jaką zajmuje algorytm, pod względem wielkości danych wejściowych do algorytmu. Często mówimy o potrzebnej „dodatkowej” pamięci, nie licząc pamięci potrzebnej do przechowywania samego wejścia. Ponownie, do pomiaru tego używamy jednostek naturalnych (ale o stałej długości).

Złożoność przestrzeni jest czasami ignorowana, ponieważ wykorzystywana przestrzeń jest minimalna i / lub oczywista, jednak czasami staje się kwestią równie ważną jak czas.

Notacje asymptotyczne

Czas wykonania algorytmu zależy od zestawu instrukcji, szybkości procesora, szybkości operacji wejścia / wyjścia dysku itp. Dlatego asymptotycznie szacujemy wydajność algorytmu.

Funkcja czasu algorytmu jest reprezentowana przez T(n), gdzie n to rozmiar wejściowy.

Do przedstawienia złożoności algorytmu używane są różne typy notacji asymptotycznych. Poniższe notacje asymptotyczne służą do obliczania złożoności czasu działania algorytmu.

• O - Wielkie Oh

• Ω - Duża omega

• θ - Big theta

• o - Trochę Oh

• ω - Mała omega

O: Asymptotyczna górna granica

„O” (Big Oh) jest najczęściej używaną notacją. Funkcjaf(n) może być reprezentowany to kolejność g(n) to jest O(g(n)), jeśli istnieje wartość dodatniej liczby całkowitej n tak jak n₀ i dodatnią stałą c takie, że -

$ f (n) \ leqslant cg (n) $ for $ n> n_ {0} $ we wszystkich przypadkach

Stąd funkcja g(n) jest górną granicą funkcji f(n), tak jak g(n) rośnie szybciej niż f(n).

Przykład

Rozważmy daną funkcję, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Biorąc pod uwagę $ g (n) = n ^ 3 $,

$ f (n) \ leqslant 5.g (n) $ dla wszystkich wartości $ n> 2 $

Stąd złożoność f(n) można przedstawić jako $ O (g (n)) $, czyli $ O (n ^ 3) $

Ω: Asymptotyczna dolna granica

Mówimy, że $ f (n) = \ Omega (g (n)) $, gdy istnieje stała c że $ f (n) \ geqslant cg (n) $ dla wszystkich wystarczająco dużych wartości n. Tutajnjest dodatnią liczbą całkowitą. Oznacza funkcjęg jest dolną granicą funkcji f; po określonej wartościn, f nigdy nie zejdzie poniżej g.

Przykład

Rozważmy daną funkcję, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.

Biorąc pod uwagę $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ dla wszystkich wartości $ n> 0 $.

Stąd złożoność f(n) można przedstawić jako $ \ Omega (g (n)) $, czyli $ \ Omega (n ^ 3) $

θ: asymptotyczna mocno związana

Mówimy, że $ f (n) = \ theta (g (n)) $, gdy istnieją stałe c₁ i c₂ że $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ dla wszystkich wystarczająco dużych wartości n. Tutajn jest dodatnią liczbą całkowitą.

Oznacza to funkcję g jest ścisłym ograniczeniem funkcji f.

Przykład

Rozważmy daną funkcję, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Biorąc pod uwagę $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ dla wszystkich dużych wartości n.

Stąd złożoność f(n) można przedstawić jako $ \ theta (g (n)) $, czyli $ \ theta (n ^ 3) $.

O - Notacja

Asymptotyczna górna granica zapewniana przez O-notationmoże, ale nie musi, być asymptotycznie ciasne. Ograniczenie $ 2.n ^ 2 = O (n ^ 2) $ jest asymptotycznie ciasne, ale ograniczenie $ 2.n = O (n ^ 2) $ nie jest.

Używamy o-notation oznaczać górną granicę, która nie jest asymptotycznie ścisła.

Definiujemy formalnie o(g(n)) (little-oh of g of n) jako zbiór f(n) = o(g(n)) dla każdej dodatniej stałej $ c> 0 $ i istnieje wartość $ n_ {0}> 0 $, taka że $ 0 \ leqslant f (n) \ leqslant cg (n) $.

Intuicyjnie w o-notation, funkcja f(n) staje się nieistotna w stosunku do g(n) tak jak nzbliża się do nieskończoności; to jest,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$

Przykład

Rozważmy tę samą funkcję, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Biorąc pod uwagę $ g (n) = n ^ {4} $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$

Stąd złożoność f(n) można przedstawić jako $ o (g (n)) $, czyli $ o (n ^ 4) $.

ω - notacja

Używamy ω-notationoznaczać dolną granicę, która nie jest asymptotycznie ścisła. Formalnie jednak definiujemyω(g(n)) (mała-omega od g od n) jako zbiór f(n) = ω(g(n)) dla każdej dodatniej stałej C > 0 i istnieje wartość $ n_ {0}> 0 $, taka że $ 0 \ leqslant cg (n) <f (n) $.

Na przykład $ \ frac {n ^ 2} {2} = \ omega (n) $, ale $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. Z relacji $ f (n) = \ omega (g (n)) $ wynika, że ​​istnieje następujący limit

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$

To jest, f(n) staje się arbitralnie duży w stosunku do g(n) tak jak n zbliża się do nieskończoności.

Przykład

Rozważmy tę samą funkcję, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Biorąc pod uwagę $ g (n) = n ^ 2 $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$

Stąd złożoność f(n) można przedstawić jako $ o (g (n)) $, czyli $ \ omega (n ^ 2) $.

Analiza Apriori i Apostiari

Analiza Apriori oznacza, że ​​analiza jest przeprowadzana przed uruchomieniem jej w określonym systemie. Analiza ta jest etapem, na którym funkcja jest definiowana za pomocą pewnego modelu teoretycznego. Dlatego określamy złożoność czasową i przestrzenną algorytmu, po prostu patrząc na algorytm, zamiast uruchamiać go w określonym systemie z inną pamięcią, procesorem i kompilatorem.

Analiza apostiari algorytmu oznacza, że ​​analizę algorytmu wykonujemy dopiero po uruchomieniu go w systemie. Zależy to bezpośrednio od systemu i zmian między systemem.

W branży nie możemy przeprowadzić analizy Apostiari, ponieważ oprogramowanie jest generalnie tworzone dla anonimowego użytkownika, który uruchamia je w systemie innym niż obecny w branży.

W Apriori jest to powód, dla którego używamy notacji asymptotycznych do określania złożoności czasu i przestrzeni, gdy zmieniają się one z komputera na komputer; jednak asymptotycznie są takie same.