Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
1 files changed, 6 insertions, 3 deletions
-rw-r--r--Seminar02/README.md9
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