![]() |
![]() |
Лёва |
![]()
Сообщение
#1
|
Гость ![]() |
Привет всем.
У меня возникла проблема. Необходимо сравнить результаты сортировки массивов разными способами с теоретическими т.е берется некий масссив к примеру из 100 эл. и сортируется одним из методов сортировки. При этом подсчитывается количество серий в массиве, количество пересылок М и количество сравнений С. С этим проблем нет. Но существуют некие формулы по которым можно теоретически расчитать минимально, среднее и максимальное количество сравнений и пересылок. Может кто поможет с пониманием вот этих выражений на конкретном значении n=100 Для прямого выбора M = 3(n-1) - ну тут конечно ясно - (n-1)=99*33=292 чтото вроде того С=n^2-n/2 - тоже понятно 4950 Метод пузырька (вот тут и начинается морока) С=n^2-n/2 - тоже как в методи прямого выбора 4950 - вопросов нет Для определения М тут нужно выявить минимальное и максимальное М а вот среднее М которое мне и нужно якобы вычисляется по вормуле Mсред=О(n^2) -так вот чему равно О? Сколько читал нигде не написано. Как выявить О, от чего оно зависит. шейкерная сортировка Mсред=О(n^2) Ссред=О(n2) Это теоретические значения они зависят от величины N т.е для них при определенных значениях N вполне можно расчитать M и C. Если конкретно то мне нужны теоретичесике цифры для 100,200,300 и 500 элементных массивов для всех видов сортировки. Кто нибудь пожалуйста объясните человеческим а не книжным языком. |
![]() ![]() |
![]() |
Текстовая версия | 21.06.2025 20:29 |