From 48823638dcdd59fc4ff4820393aee833208155e4 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Sun, 25 Dec 2022 18:19:37 +0200 Subject: Fixed typos --- Seminar04/README.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'Seminar04') diff --git a/Seminar04/README.md b/Seminar04/README.md index 18eae0d..efa7539 100644 --- a/Seminar04/README.md +++ b/Seminar04/README.md @@ -99,7 +99,7 @@ std::vector filter(const std::vector& arr, bool (*pred)(int)) { ``` ## Сложността на push_back -До момента разгледахме няколко структури от данни и се стремяхме главно към O(1) сложност. Виждоме, че push_back() е доста използвана операция, каква е нейната сложност? Ами тя доста често е константна, но когато ни се наложи да направим алокация е линейна. Тоест, в най - лошия случай тя е O(n). Но това не е достатъчно добра оценка. +До момента разгледахме няколко структури от данни и се стремяхме главно към O(1) сложност. Виждаме, че push_back() е доста използвана операция, каква е нейната сложност? Ами тя доста често е константна, но когато ни се наложи да направим алокация е линейна. Тоест, в най - лошия случай тя е O(n). Но това не е достатъчно добра оценка. В случая worst case сложността е твърде песимистична. Интересува ни по - скоро колко време ще отнеме цялото изпълнение на алгоритъма използващ push_back() а не колко време ще отнеме на 17 стъпка, примерно. Приемаме по - оптимистичен подход - нека не се интересуваме от това колко е най - лошия случай на операцията а да разгледаме колко време ни отнема да направим всички операции. Това неформално е целта на така наречения амортизиран анализ на сложност. С него няма да се занимаваме особено много, но е добре да го знаем от обща култура. @@ -204,4 +204,4 @@ LL = 1 -> 5 -> 2 -> 4 -> 3 * Имате празен списък * Имате списък с един елемент * Имате списък и четни елементи -* Имате списък с нечетни елементи \ No newline at end of file +* Имате списък с нечетни елементи -- cgit v1.3.1-23-gd82d