Оценка трудоемкости сортировки массивов Опции

[Лёва]

Привет всем.

У меня возникла проблема.
Необходимо сравнить результаты сортировки массивов разными способами с теоретическими
т.е берется некий масссив к примеру из 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 элементных массивов для всех видов сортировки.
Кто нибудь пожалуйста объясните человеческим а не книжным языком.

[andriano]

У тебя здесь некоторая путаница.
Во-первых, если "Необходимо сравнить результаты сортировки массивов", то это означает, что мы берем именно результаты, т.е. отсортированные массивы, и сравниваем их между собой. У такого сравнения могут быть две цели:
1. Проверить правильность работы алгоритма.
2. Проверить, переставляет ли алгоритм местами объекты с равным значением метрики. (например, при выводе 3D-сцены сортируем полигоны по расстоянию от камеры и нам нужно знать, как будут расположены друг относительно друга полигоны, находящиеся на одинаковом расстоянии от камеры)

Далее. Есть подозрение, что тебя интересует не результат работы, а сложность алгоритма. Сложность выражается не в точном количестве операций, а в том, подобно какой функции ведет себя количество операций при устремлении длины сортируемого массива к бесконечности.
O(n^2) означет не O*n^2, а лишь то, что количество операций может быть выражено как
k1*n^2 + k2*n*ln(n) + k3*n + k4*ln(n) + k5
где k1,k2,k3,k4,k5 - некоторые константы
(возможен вариант формулировки: начиная с некоторого N, не превосходит k0*n^2)
Естественно, при устремлении n к бесконечности всеми членами кроме квадратичного (если коэффициент при нем не равен 0) можно пренебречь.
Для разных алгоритмов конкретные величины k0...k5 могут быть совершенно различны. Из-за этого при небольших n (например, 100 или 500) алгоритм, имеющий меньшую сложность, может содержать бОльшее количество операций (и, соответственно, работать дольше).

Таким образом тебе следует понять разницу между точным количеством операций и сложностью, представляющей собой асимптотическую оценку.

Теперь насчет максимальных и минимальных.

У пузырька ход выполнения алгоритма не зависит от исходных данных. Поэтому количество операций сравнения всегда одинаков. У многих же более совершенных алгоритмов нередко ход выполнения алгоритма зависит от сортируемой последовательности. В частности, может оказаться, что если мы проведем несколько экспериментов на нескольких случайных выборках, то результат будет примерно соответствовать зависимости n*ln(n), но в наихудшем случае будет достигать n^2. В то же воремя вменяемый алгоритм сортировки долже уметь понять, что массив отcортирован, и с ним ничего не нужно делать за O(n) операций. Поэтому может оказаться, что некий алгоритм работает в наилучшем случае за O(n), в среднем за O(n*ln(n)) и в худшем - за O(n^2).
Соответственно, если в наилучшем и наихудшем случае можно дать точную численную оценку (просто осчитав количество операций в лучшем и худшем случае), для среднего можно дать лишь оценку сложности и примерно оценить величину константы.

[Michael_Rybak]

У пузырька ход выполнения алгоритма не зависит от исходных данных.

О_О