From 0f27023b9c30f23936ee706fa5f10f91c4331deb Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 20 Oct 2024 07:51:36 -0400 Subject: Fix formatting --- Seminar02/README.md | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/Seminar02/README.md b/Seminar02/README.md index 1ffcc53..bf4c009 100644 --- a/Seminar02/README.md +++ b/Seminar02/README.md @@ -31,9 +31,8 @@ void sum_rec(int* arr, unsigned size, int& sum) * T(n) = T(n - 1) + 1 Решение на рекурентно уравнение наричаме затворена формула. Решение на горния пример би било: -$$ + T(n) = n + 1 -$$ ## Методи за решаване на рекурентни уравнения @@ -71,7 +70,7 @@ $$ ## Примери Нека разгледаме някои примери за рекурентни уравнения. -$$ +$$ T(0) = \theta(1) \newline T(n) = 3T(n - 1) + \theta(1) @@ -81,6 +80,7 @@ $$ ![tree-recur](media/recurr2.png) Нивата на това дърво ще са n на брой. Всеки елемент е с единица по - малък от баща си. Също така, на всяко ниво има 3^j върха, където j е номерът на нивото (номерираме от 0). Всеки възел извършва Θ(1) работа. Сумираме по нива: + $$ \sum_{i = 0}^n 3^i * \theta(1) = \frac{3^{n + 1} - 1}{2} * \theta(1) = \theta(3^n) $$ @@ -112,8 +112,11 @@ $$ Сложността на `Merge Sort` се описва чрез рекурентната редица, използвана като пример за решение използващо метода с дърво на рекурсията. И в трита случая имаме Θ(n log(n)) Стабилен - Да + Адаптивен - Не + in-place - Не + Сложност по памет - Θ(n) ## Алгоритъмът Quick Sort \ No newline at end of file -- cgit v1.3.1-23-gd82d