|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
06.09.2015, 14:21 | #1 |
Пользователь
Регистрация: 30.11.2014
Сообщений: 65
|
оценка алгоритмов сортировки
Пожалуйста, помогите понять как оценивать сортировки.
Приведён пример, уже подсчитанный, а как это сделать не совсем понятно. Вот пример из литературы: "К сожалению как и в сортировке пузырьковым методом внешний цикл сортировки выбором выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). В лучшем случае /когда исходный массив уже упорядочен/ потребуется поменять местами только n-1 элементов,а каждая операция обмена требует три операции пересылки." |
06.09.2015, 15:00 | #2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Единственное что могу сказать: https://ru.wikipedia.org/wiki/%D0%92...81%D1%82%D1%8C
Ну то-есть логарифмы считать придется, как я понял.
I'm learning to live...
|
06.09.2015, 15:35 | #3 | |
мальчик-помогай =)
Форумчанин
Регистрация: 16.09.2010
Сообщений: 522
|
Цитата:
Код:
теперь нам нужен поиск в массиве.... код в лоб: Код:
- если Х находится в первом элементе, то цикл выполнит 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) и спать спокойно если же данные сложные (строки, например), то тут начинает вступать в силу оценка количества сравнений и может понадобиться алгоритм, который имеет большую сложность, но меньшее количество сравнений (это в теории, а так-то оптимизируют сравнение, вводя всякие хеш-поля, которые сравнить в разы дешевле, чем сами данные) Последний раз редактировалось GreenWizard; 06.09.2015 в 15:50. |
|
06.09.2015, 17:31 | #4 |
Пользователь
Регистрация: 30.11.2014
Сообщений: 65
|
GreenWizard, спасибо! Стало понятнее.
|
07.09.2015, 03:46 | #5 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Подробно анализ сортировки пузырьком и выбором описан в статье "Анализ сложности алгоритмов". Анализ рекурсивных вариантом быстрой сортировки и сортировки слиянием разобран в статье "Анализ рекурсивных алгоритмов".
|
07.09.2015, 06:53 | #6 | |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Цитата:
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
|
07.09.2015, 10:18 | #7 | |
Пользователь
Регистрация: 30.11.2014
Сообщений: 65
|
Цитата:
|
|
07.09.2015, 10:50 | #8 |
Пользователь
Регистрация: 16.05.2008
Сообщений: 46
|
На эту тему есть классическая книга: Д. Кнут "Искусство программирования" том 3 "Сортировка и поиск". В книге много информации и богатый математический арсенал сравнения различных методов сортировок. Дерзайте!
|
07.09.2015, 12:28 | #9 |
Старожил
Регистрация: 31.05.2010
Сообщений: 13,543
|
Ненавижу Кнута. Запутал так, что я чуть не бросл заниматься С++. Благо, выкинул его в окно и начал заниматься самообразованием.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder |
07.09.2015, 12:38 | #10 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как понимают эффективность алгоритмов сортировки? | Proskurina | Общие вопросы по программированию, компьютерный форум | 0 | 16.11.2012 10:29 |
Сравнить эффективность алгоритмов шейкерной сортировки и сортировки слиянием (язык C) | Ольга210993 | Помощь студентам | 2 | 20.09.2012 13:52 |
исследование Алгоритмов Сортировки | Camaro Chevelle | Помощь студентам | 5 | 06.11.2011 21:59 |
Сравнение алгоритмов сортировки массива | Семен_Владимирович | Общие вопросы C/C++ | 2 | 15.02.2011 19:02 |
Оценка сложности алгоритмов | Kristen_McBrian | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 22.12.2010 02:09 |