diff options
Fixed typos
1 files changed, 2 insertions, 2 deletions
| -rw-r--r-- | Seminar04/README.md | 4 |
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<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 стъпка, примерно. Приемаме по - оптимистичен подход - нека не се интересуваме от това колко е най - лошия случай на операцията а да разгледаме колко време ни отнема да направим всички операции. Това неформално е целта на така наречения амортизиран анализ на сложност. С него няма да се занимаваме особено много, но е добре да го знаем от обща култура. @@ -204,4 +204,4 @@ LL = 1 -> 5 -> 2 -> 4 -> 3 * Имате празен списък * Имате списък с един елемент * Имате списък и четни елементи -* Имате списък с нечетни елементи
\ No newline at end of file +* Имате списък с нечетни елементи |