diff options
pls no more merge conficts
1 files changed, 5 insertions, 3 deletions
| -rw-r--r-- | Seminar04/README.md | 8 |
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 +* Имате списък с нечетни елементи |
