diff options
Fix formatting
1 files changed, 6 insertions, 3 deletions
| -rw-r--r-- | Seminar02/README.md | 9 |
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 @@ $$  Нивата на това дърво ще са 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 |