diff options
2 files changed, 10 insertions, 11 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf | bin | 60083 -> 60370 bytes | |||
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex | 21 |
diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf Binary files differindex b96b97e..c76c68b 100644 --- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf +++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex index 762021e..53f2a54 100644 --- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex +++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex @@ -113,9 +113,7 @@ \section{Решение} -$\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[1..n]$. Тоест, $\textsc{SomeAlg}(A, 1, n)$ ще сортира целия масив. - -\hfill +$\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[1..n]$. Тоест, $\textsc{SomeAlg}(A, 1, n)$ ще сортира целия масив $A[1..n]$. Ще докажем коректността на алгоритъма с индукция по $h-l$ (което се явява дължината на нашия подмасив минус едно). @@ -137,14 +135,15 @@ $\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[ На ред 8 сортираме всички останали елементи, които са в $\alpha\beta$ (и са по-малки от тези в $\gamma$). \newline Така целия подмасив е вече сортиран. \end{enumerate} - + +\hfill + Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2 до 5 той извършва работа, която не зависи от входа, тоест константа работа $c$, докато на редове 6 до 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде: -\begin{align*} - T(n) = 3T\left(\frac{2}{3}n\right) + c -\end{align*} -Тогава: -\begin{align*} - a = 3, b = \frac{3}{2}, f(n) = c \quad \text{За } \varepsilon = 1, f(n) \preceq \frac{n^{\log_\frac{3}{2} 3}}{n}, \log_\frac{3}{2} 3 - 1 > 0 \xRightarrow[]{\text{1 случай на Мастър Теоремата}} T(n) \asymp n^{\log_\frac{3}{2} 3} -\end{align*} +\begin{gather*} + T(n) = 3T\left(\frac{2}{3}n\right) + c \text{, тогава} \\ + a = 3, b = \frac{3}{2}, f(n) = c \quad \text{За } \varepsilon = 1, f(n) \preceq \frac{n^{\log_\frac{3}{2} 3}}{n}, \log_\frac{3}{2} 3 - 1 > 0 \xRightarrow[\text{Мастър Теоремата}]{\text{1 случай на}} T(n) \asymp n^{\log_\frac{3}{2} 3} +\end{gather*} + +Проф. Дълбоков не е прав, проверката е нужна, понеже иначе $h - l \leq 0$ и на ред 4: $t \leq 0$, тоест условието на ред 5 никога няма да бъде изпълнено и алгоритъмът ще завърши без да сортира масива. \end{document}
\ No newline at end of file |