оценка алгоритмов сортировки

[Asya7]

Пожалуйста, помогите понять как оценивать сортировки.
Приведён пример, уже подсчитанный, а как это сделать не совсем понятно.
Вот пример из литературы: "К сожалению как и в сортировке пузырьковым методом внешний цикл сортировки выбором выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). В лучшем случае /когда исходный массив уже упорядочен/ потребуется поменять местами только n-1 элементов,а каждая операция обмена требует три операции пересылки."

[Stilet]

Единственное что могу сказать: https://ru.wikipedia.org/wiki/%D0%92...81%D1%82%D1%8C
Ну то-есть логарифмы считать придется, как я понял.

[GreenWizard]

Сообщение от Asya7

Пожалуйста, помогите понять как оценивать сортировки.
Приведён пример, уже подсчитанный, а как это сделать не совсем понятно.
Вот пример из литературы: "К сожалению как и в сортировке пузырьковым методом внешний цикл сортировки выбором выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). В лучшем случае /когда исходный массив уже упорядочен/ потребуется поменять местами только n-1 элементов,а каждая операция обмена требует три операции пересылки."

я приведу пример чуть оторванный от темы.... скажем, есть массив А и нужно к каждому элементу его прибавить Х.... код:

for i := 0 to N - 1 do
  A[i] := A[i] + X;

какова сложность этого кода? Внутреннее тело цикла будет выполнено ровно N раз, не зависимо от содержимого массива и от Х, поэтому O(N).
теперь нам нужен поиск в массиве.... код в лоб:

for i := 0 to N - 1 do
  if A[i] = X than нашли

тут у нас уже есть худший и лучший вариант:
- если Х находится в первом элементе, то цикл выполнит 1 итерацию и 1 сравнение
- если Х нету в массиве, то мы выполним N итераций и N сравнений
таким образом, оценка тут O(1) и O(N)

если массив упорядочен, то мы можем применить бинарный поиск, который каждый раз сокращает проверяемую область в 2 раза, а проверяет 1 элемент всего (центральный) на равенство Х и на больше/меньше (2 проверки, если наивная реализация) т. е. для массива из N элементов имеем:
- N/2; 1 итерация; 2 сравнения;
- N/4; 1 итерация; 2 сравнения;
- N/8; 1 итерация; 2 сравнения;
- N/16; 1 итерация; 2 сравнения;
- N/32; 1 итерация; 2 сравнения;
................................... ...............
- N/ 2^n, где n такое, что 2^n < N < 2^(n + 1); 1 итерация; 2 сравнения;
если найти лимит этого безобразия, то получим, что в худшем случаем потребуется log2(N) итераций и 2*log2(N) сравнений

простые алгоритмы легко оценить на глаз, но зачастую требуется мат. анализ, оценка вероятностей худшего/лучшего варианта, оценка работы на "типичных" данных и в "краевых" условиях, когда данные максимально "плохие" (у бин. поиска есть вариант с интерполяцией и он часто работает быстрее обычного, но если мы имеем много одинаковых элементов, то он будет работать так же "плохо" как и обычный + потребуется время на интерполяцию т. е. его log2(N) хуже log2(N) бинарного поиска, но средняя оценка лучше)

---------------------------------------
если данные просты, то время сравнение мало и можно принять время работы поиска за T*log2(N) и спать спокойно
если же данные сложные (строки, например), то тут начинает вступать в силу оценка количества сравнений и может понадобиться алгоритм, который имеет большую сложность, но меньшее количество сравнений (это в теории, а так-то оптимизируют сравнение, вводя всякие хеш-поля, которые сравнить в разы дешевле, чем сами данные)

[Asya7]

GreenWizard, спасибо! Стало понятнее.

[rrrFer]

Подробно анализ сортировки пузырьком и выбором описан в статье "Анализ сложности алгоритмов". Анализ рекурсивных вариантом быстрой сортировки и сортировки слиянием разобран в статье "Анализ рекурсивных алгоритмов".

[Smitt&Wesson]

оценка алгоритмов сортировки

Таааак, похоже мне пора вешаться. И для кого я это пишу? Не понятно.

[Asya7]

Сообщение от Smitt&Wesson

И для кого я это пишу? Не понятно.

Спасибо, но мне кажется, что там у вас просто приведён пример сравнения работ различных сортировок. А мне нужно объяснение по методу вычислению оценки работы. ( выше в сообщениях - мне уже примерно стало понятно, как делается)

[promer]

На эту тему есть классическая книга: Д. Кнут "Искусство программирования" том 3 "Сортировка и поиск". В книге много информации и богатый математический арсенал сравнения различных методов сортировок. Дерзайте!

[Smitt&Wesson]

Сообщение от promer

На эту тему есть классическая книга: Д. Кнут "Искусство программирования" том 3 "Сортировка и поиск". В книге много информации и богатый математический арсенал сравнения различных методов сортировок. Дерзайте!

Ненавижу Кнута. Запутал так, что я чуть не бросл заниматься С++. Благо, выкинул его в окно и начал заниматься самообразованием.

[Аватар]

Благо, выкинул его в окно и начал заниматься самообразованием.

Да, он толстый, если в окно да по голове кому-то, то слабо не покажется Дома до сих пор три тома где-то валяется, каждый по кг с лишним