Упражнение 1

Алгоритъм. Сложност. Асимптотични Означения.

Алгоритъм

Какво е алгоритъм? Ами всъщност, този въпрос излиза извън рамките на курса :) Обаче като за в рамките на ДАА можем да считаме, че алгоритъмът е черна кутия, която преработва входни данни до изходни данни. Също така работи дискретно - т.е във всеки един момент се намира в някакво състояние, а в следващия (дискретен) момент преминава във следващото състояние, и така до края. Край се дефинира с някакво крайно състояние(например, намерен е отговор) За нуждите на курса ще се интересуваме само от алгоритми, които винаги приключват изпълнението си.

Входните данни ще ги разглеждаме на групи. Ще отъждествяваме всякакви входни данни с някое естествено число, което всъщност ще измерва размера на входа. Ако например сме написали програма, която сортира естествени числа, една възможна мярка е - броят естествени числа определя размера на входа. Обърнете внимание, че е възможно в една група да влизат безкраен брой входни данни (колко различни двойки естествени числа съществуват - всички те ще бъдат в групата с размер 2). Технически, правилният начин за измерване на входните данни е в битове - колко бита се използват за кодиране на данните. На практика, по-удобно е по други начини. По-информативно е, че сортираме 13 числа, отколкото 416 бита.

Един алгоритъм е интересен (от гледна точка на математиката) в няколко аспекта:

  • коректност - т.е дали решава зададената задача (или играе Quake 3 докато не го гледаме)
  • времева сложност - т.е за колко стъпки ще завърши изпълнението си. Обърнете внимание, че алгоритмите работят винаги за някакъв цяло число брой стъпки което може да бъде измерено. Един двигател с вътрешно горене не може да бъде измерен по този начин, защото не работи на дискретни стъпки.
  • пространствена сложност - колко памет заемат, докато завършат. Това разбира се зависи силно от начина по който дефинираме и мерим памет, но и без това няма да се занимаваме с това в този курс - стига толкова по въпроса.

В ДАА ще се занимаваме с измерване на времева сложност (или още - бързодействие) на алгоритмите1. Обърнете внимание, че искаме да разглеждаме бързодействието като функция на големината на входа. С горния пример - колко операции извършва алгоритъмът за сортиране на n числа като функция на n. Бързодействието може да се мери по няколко начина:

  • в най-лошия случай (worst-case) - т.е от всички входни данни в дадена група изчислим коя точно входна данна кара алгоритъма да извърши най-много стъпки.
  • средна стойност (average) - т.е ако вземем всички входни данни в дадена група, изчислим за колко време работи алгоритъмът над тях, и вземем средното аритметично на всичко това, ще получим средната стойност2.

Спокойно - след малко ще видите, че не е нужно да сме толкова педантични - достатъчно е да хванем общата идея на функцията и в двата случая. Ще се занимаваме основно с worst-case времева сложност - тъй като по-лесно се анализира математически - а за average вероятно няма да остане време.
Дам, след 12 години училище, година и половина университет - все още вършим само най-елементарните математически дейности. Йей.

Асимптотичен анализ

Моля не се стресирайте, макар в горния израз по-ясната от 2те думички да е анализ :)
Когато анализираме поведението на дадена функция (например времева сложност), доста по-удачно е вместо да се стремим да намерим точния вид на функцията, който примерно изглежда така: $T(n) = 12 n^2 + 94 n + 30940$ да се задоволим просто с $n^2$.

Защо??

Защо го правим - ами защото практиката е показала, че от много издребняване няма особен смисъл. Науката също го е доказала - при достатъчно голямо N някои функции доминират други(стават безкрайно по-значими). Например, функцията на времето: $T(n) = n^2 + 94 n$. Някоя програма прави $n^2 + 94n$ стъпки когато входът е с размер N. При n < 94 първата степен "отнема повече време" от втората(т.е. $94n > n^2$). Но, с нарастването на N, тя става все по-маловажна. При n = 1000 първата степен вече отговаря за 9 процента от цялото време отделено за смятане. Когато N клони към безкрайност, втората степен отговаря за ~100% от цялото време. В този предмет терминът време се използва по този начин, да. Т.е. $N^2$ не означава да се сметне числото $N^2$, а да се направят толкова стъпки.

Сега ще се научим как точно да сравняваме функциите по един малко по-либерален начин - такъв че функцията $12 n^2 + 94 n + 30940$ да е равна на функцията $n^2$.

Никоя уважаваща себе си математическа наука не започва без солидно количество…

Дефиниции

Ще дефинираме следното чудо - на функция съпоставяме множество функции. Може да си мислим, че всяка функция от множеството е равна(в някакъв смисъл) на $g(n)$.

(1)
\begin{align} \Theta(g(n)) = \{ f(n) | \exists c_1, c_2 \in \mathbb R_+\ \exists n_0 \in \mathbb N : \forall n \ge n_0 \quad 0 \le c_1 g(n) \le f(n) \le c_2 g(n) \} \end{align}

Това се чете по следния начин:
Тита от g(n) е равно на множеството от всички функции, за които съществуват две константи такива, че за достатъчно големи N всяка стойност на N, f(n) е в интервала $[c_1 g(n) : c_2 g(n)$. Тези константи не са едни за цялото множество - за всяка функция се избират поотделно. Например, при $g(n) = n^2$, а $f(n) = \sqrt{3} n^2$, можем да вземем C1 = 1, C2 = 2 и N0 = 1. Та, множеството се състои от всички функции, за които това може да се направи. Нулата горе е важна, впрочем. Асимптотичните нотации се гледат само в положителни стойности. Тоест, трябва да си гарантираме, че от някой момент нататък функциите са по-големи от нула.

Ще записваме $T(n) \in \Theta(n^2)$ или по-скоро $T(n) = \Theta(n^2)$. С което всъщност ще казваме, че $T(n)$ е горе долу $n^2$ и за нуждите на курса направо ще игнорираме дребните различия :) (това разбира се е пример - на мястото на n^2 може да стои която си поискате функция).
Това може би е очевидно, но все пак:
В асимптотична нотация константите нямат значение. O(12n) = O(n).

Ще разгледаме и останалите 4 дефиниции и почваме задачииии (:
Дефиниция(главно O или още горна граница):
Всички функции, които са толкова бавни или по-бързи от g(n):

(2)
\begin{align} O(g(n)) = \{ f(n) | \exists c > 0\ \exists n_0 > 0 : \forall n \ge n_0 \quad 0 \le f(n) \le cg(n) \} \end{align}

Дефиниция(омега или още долна граница):
Всички толкова бавни или по-бавни:

(3)
\begin{align} \Omega(g(n)) = \{ f(n) | \exists c > 0\ \exists n_0 > 0 : \forall n \ge n_0 \quad 0 \le cg(n) \le f(n) \} \end{align}

Дефиниция(малко O):3
По-бързите от g(n)

(4)
\begin{align} o(g(n)) = \{ f(n) | \forall c > 0 \ \exists n_0 > 0 : \forall n \ge n_0 \quad 0 \le f(n) < cg(n) \} \end{align}

Дефиниция(малка омега):4
По-бавните:

(5)
\begin{align} \omega(g(n)) = \{ f(n) | \forall c > 0 \ \exists n_0 > 0 : \forall n \ge n_0 \quad 0 \le cg(n) < f(n) \} \end{align}

Забележка: Както споменахме по-горе - вместо да пишем, че дадена функция принадлежи на някой от горните класове, ще пишем просто равно (от гледна точка на теория на множествата не е коректно, но хайде сега).

Крайно време е да решим малко

Задачи

Задача 1

Да се докаже, че : $\frac{1}{2}n^2 - 3n = \Theta(n^2)$.
Решение:

Задача 2

Нека $p(n) = a_d n^d + a_{d-1} n^{d-1} + \cdots + a_1 n + a_0$ и $a_d \ne 0$.
Да се докаже, че $p(n) = \Theta(n^d)$.
Решение:

Задача 3

Нека функциите $f(n), g(n)$ са асимптотично положителни (т.е за достатъчно голямо $n$ са положителни).
Да се докаже, че $\max(f(n), g(n)) = \Theta(f(n) + g(n))$.
Забележка: В тази клопка е по-вероятно да попаднат хората, които са използвали до сега означения като $\Theta$6 когато говорят за сложност на алгоритми (т.е ако за първи път чувате всичко това може да не четете забележката) . Задачата тук не е да се намери сложността на функцията максимум - просто трябва да се покаже, че максимумът (бидейки в случая функция на един аргумент - $n$) е функция, която принадлежи на сложностния клас $\Theta(f(n) + g(n))$.

Решение:

Задача 4

Нека $a, b \in \mathbb R \And b > 0$.
Да се докаже, че $(n + a)^b = \Theta(n^b)$.
Решение:

Задача 5

Да се провери:
a) $2^{n+1} = O(2^n)$
b) $2^{2n} = O(2^n)$
Решение:

Апроксимация на Стирлинг

Тъй като факториелът е малко шантава функция (т.е ние много добре си знаем какво означава и как се пресмята, но не е удобна за асимптотична нотация) ще я апроксимираме малко (на български язък - ще намерим нейно приближение) така че да е по-удобно да намираме логаритъм от нея. Използваме формулата на Стирлинг:

(12)
\begin{align} n! \approx \sqrt{2\pi n} \frac{n^n}{e^n}(1 + \Theta(\frac{1}{n})) \end{align}

Тук под $\Theta(\frac{1}{n})$ разбираме някоя точно конкретна функция в този клас, която е различна за всяко $n$. Всъщност самата апроксимация е без този последния член с титата, обаче така получаваме явна представа от това колко точно е грешката. Вижте тук за повече информация.

Сега вече спокойно можем да сметнем колко е $O(\lg(n!))$:

(13)
\begin{align} O(\lg(n!)) = O(\lg \sqrt{2\pi} + \frac{1}{2}\lg n + \lg n^n + \lg e^n) = O(n \lg n) \end{align}

(Всичко бива доминирано от $\lg n^n$)

Задача 6

За следните функции F и G да се определи кои означения удовлетворяват при $k \ge 1\ \epsilon > 0\ c > 1$
(Има се предвид дали е вярно $F = O(G), F = \Omega(G)$ и т.н.
a) $\lg^k n \quad n^\epsilon$
b) $n^k \quad c^n$
c) $\sqrt{n} \quad n^{\sin n}$
d) $2^n \quad 2^{\frac{n}{2}}$
e) $\lg(n!) \quad \lg(n^n)$

Решение:

Задача 7

Подредете следните функции в намаляващ асимпотичен ред (т.е всяка следваща да е $o$ от предходната (или всяка предходна да е $\omega$ от следващото)).

(14)
\begin{matrix} \lg(\lg^\star n) & \left(\frac{3}{2}\right)^n & \ln\ln n & 2^{\lg n} & \lg^\star\lg n \\ 2^{\lg^\star n} & n^3 & \lg^\star n & (\lg n)^{\lg n} & 2^{\sqrt{2 \lg n}} \\ (\sqrt{2})^{\lg n} & \lg^2 n & n2^n & e^n & n \\ n^2 & \lg n! & n^{\lg \lg n} & 4^{\lg n} & 2^n \\ n! & 2^{2^{n}} & \ln n & (n+1)! & n\lg n \\ (\lg n)! & n^{\frac{1}{\lg n}} & 1 & \sqrt{\lg n} & 2^{2^{n+1} \end{matrix}

Решение:

gi
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License