Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar04
diff options
context:
space:
mode:
Commit46a31d1c2bfeca7429df19a5e989a52b665b0bb3 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:01:53 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 18:01:53 +0200
Files84c78178afbc28d74edaf0918cfb3c3fb273e23a /Seminar04
Data-structures-and-algorithms-46a31d1c2bfeca7429df19a5e989a52b665b0bb3.tar
Data-structures-and-algorithms-46a31d1c2bfeca7429df19a5e989a52b665b0bb3.tar.gz
Data-structures-and-algorithms-46a31d1c2bfeca7429df19a5e989a52b665b0bb3.zip
Parent63f4cb943f81c257e78ebeef828edbc04e78264b (diff)
Parent76904781d28d13e321c48827680bdb0d7c039bd9 (diff)
pls no more merge conficts
1 files changed, 5 insertions, 3 deletions
-rw-r--r--Seminar04/README.md8
diff --git a/Seminar04/README.md b/Seminar04/README.md
index 18eae0d..eb35f37 100644
--- a/Seminar04/README.md
+++ b/Seminar04/README.md
@@ -64,7 +64,7 @@ class DynArray {
size_t capacity = 8;
};
```
-Нека в началото *capacity* да е 8. Кога ще имаме алокация? Първо, ще алокираме памет при създаването на масива. След това, когато се опитаме да добавим девети елемент ще алокираме 16 * sizeof(T) байта. След това когато се опитаме да добавим седемнадесети елемент ще алокираме 32 * sizeof(T) байта.
+Нека в началото *capacity* да е 8. Кога ще имаме алокация? Първо, ще алокираме памет при създаването на масива. След това, когато се опитаме да добавим девети елемент ще алокираме 16 \* sizeof(T) байта. След това когато се опитаме да добавим седемнадесети елемент ще алокираме 32 \* sizeof(T) байта.
Тоест, когато въртя for цикъла във втория пример, всеки път когато *i = 2^k + 1* ще имам алокация на памет.
Това за наше щастие има как да се оправи. Когато знаем колко елемента ще пазим в динамичния масив можем да извикаме *resize(size_t)*.
@@ -99,7 +99,7 @@ std::vector<int> filter(const std::vector<int>& arr, bool (*pred)(int)) {
```
## Сложността на push_back
-До момента разгледахме няколко структури от данни и се стремяхме главно към O(1) сложност. Виждоме, че push_back() е доста използвана операция, каква е нейната сложност? Ами тя доста често е константна, но когато ни се наложи да направим алокация е линейна. Тоест, в най - лошия случай тя е O(n). Но това не е достатъчно добра оценка.
+До момента разгледахме няколко структури от данни и се стремяхме главно към O(1) сложност. Виждаме, че push_back() е доста използвана операция, каква е нейната сложност? Ами тя доста често е константна, но когато ни се наложи да направим алокация е линейна. Тоест, в най - лошия случай тя е O(n). Но това не е достатъчно добра оценка.
В случая worst case сложността е твърде песимистична. Интересува ни по - скоро колко време ще отнеме цялото изпълнение на алгоритъма използващ push_back() а не колко време ще отнеме на 17 стъпка, примерно. Приемаме по - оптимистичен подход - нека не се интересуваме от това колко е най - лошия случай на операцията а да разгледаме колко време ни отнема да направим всички операции.
Това неформално е целта на така наречения амортизиран анализ на сложност. С него няма да се занимаваме особено много, но е добре да го знаем от обща култура.
@@ -187,9 +187,11 @@ LL = 5 -> 4 -> 3 -> 2 -> 1
Да се напише функция, която открива средата на свързан списък.
Пример:
+```
1 -> 2 -> 3 -> 4 -> 5 => 3
1 -> 2 -> 3 -> 4 => 3
+```
## Задача четвърта
да се напише функция която пренарежда свързания списък по следния начин:
@@ -204,4 +206,4 @@ LL = 1 -> 5 -> 2 -> 4 -> 3
* Имате празен списък
* Имате списък с един елемент
* Имате списък и четни елементи
-* Имате списък с нечетни елементи \ No newline at end of file
+* Имате списък с нечетни елементи