Существует множество способов решения определенной задачи (класса задач). Это множество порождает обилие алгоритмов, которые ее решают. Однако из этого набора алгоритмов можно выбрать те, которые справляются с поставленной задачей (классом задач) быстрее остальных, используя меньше ресурсов процессора и /или оперативной памяти. Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения. Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным. В качестве примера рассмотрим алгоритм сортировки массива методом вставки. Помимо этого я покажу как лучше оформлять сообщение, содержащее обзор алгоритма. Сортировка массива методом вставки. 1. Псевдокод (справка: _http://ru.wikipedia.org/wiki/Псевдокод_(язык_описания_алгоритмов)), описывающий рассматриваемый алгоритм. Code: InsertionSort(list, N) list //исходный массив N //количество элементов в массиве for j = 2 to N do newelement = list[j]; location = j - 1; while (location >= 1) and (list[location]>newelement) list[location + 1] = list[location]; location = location - 1; end while; list[location + 1] = newelement; end for; 2. Оценка временной сложности. Временная сложность - скорость увеличения числа операций при возрастании размерности задачи. Например, пусть алгоритм содержит внешний цикл C1 с числом операций N1 и внутренний цикл C2 с числом операций N2, тогда временная сложность определяется следующим образом: Code: T(N) = C1 * N1 * C2 * N2 ~= С1 * С2 * (N^2) = O (N^2). Скорость определяется элементом, стоящим в скобках. Применим формулу к рассматриваемому алгоритму. В лучшем случае (когда элементы массива уже упорядочены: [1, 2, 3, 4]): Code: T(N) = O (N). В худшем случае (все элементы массива расположены в обратном порядке: [4, 3, 2, 1]): Code: T(N) = O ((N^2)/4). 3. Вывод. Алгоритм сортировки методом вставки является наиболее быстродейственным для небольших массивов, с высокой степенью начальной упорядоченности.
Сортировка массива методом перестановки.Дан массив из n чисел, отсортировать его по возврастанию. Решение: Будем генерировать все возможные перестановки из n элементов. Среди всех возможных перестановок из n эл., существует такая в которой элементы расставлены в неубывающем порядке. Завершаем алгоритм. Временная сложность. В худшем случае требуется перебрать n! перестановок. Вывод. Более неэффективного алгоритма сортировки не существует. ----------------------- 2ErrorNeo Предложенный тобой алгоритм не решает задачу сортировки массива, т.к. он не всюду применим(он может не отсортировать данный массив за конечное время, т.е. мы не узнаем работает алгоритм или нет =) )
существует. можно генерировать рандомные варианты перестановок из n эл. до тех пор, пока массив не окажется упорядоченным. Если повезет - такой метод перестановки отработает всю сортировку за 1 перестановку. Если нет- решение может занять намного дольше твоего метода, т.к. каждая новая попытка в данном случае не увеличивает вероятности "успешного попадания". А вообще самый быстрый из существующих методов сортировки массивов называется "quicksort" http://ru.wikipedia.org/wiki/Быстрая_сортировка метод описанный в первом посте - http://ru.wikipedia.org/wiki/Сортировка_вставками
Не соглашусь... У быстрой сортировки в худшем случае O(N^2), а в среднем O(N*log N). У пирамидальной сортировки в любом случае (тоесть и в лучшем, и в худшем, и в среднем) O(N*log N). Так же существует еще и поразрядная сортировка, которая вообще линейна...
Сортировка методом "пузырька". 1. Псевдокод. Code: NOF = N; SE = true; while SE do NOF = NOF -1; SE= false; for i = 1 to NOF do if list[i] > list[i + 1] then swap(list[i], list[i+1]);//поменять местами SF = true; end if end for end while. 2. Оценка временной сложности. В лучшем случае (все элементы уже упорядоченны): Code: T(n) = O(N) В худшем случае (элементы расположены в обратном порядке): Code: T(n) = (N - 1) + (N - 2) + ... + 1= O(N^2) 3. Вывод. Простой алгоритм сортировки, эффективный для небольших массивов, однако, прост для понимания и легок для реализации.
Сортировка простым выбором. 1. Псевдокод Code: var lowkey: keytype; lowindex: integer; Begin for i = 1 to (n -1) do lowindex = j; lowkey = A[j].key; for k = j + 1 to N do if A[k].key < lowkey then lowkey = A[k].key; lowindex = k; end if; swap (A[j], A[lowindex]);//поменять местами end for; end. 2. Оценка эффективности. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае: Code: T(n) = O(N^2) (c) Wikipedia 3. Вывод. Неустойчивый алгоритм сортировки, обладающий одинаковым временем сортировки для небольших массивов разной степени упорядоченности, что делает его наиболее универсальным в своем классе.
Сортировка Шелла. 1. Псевдокод. Code: ShellSort(list, N) list//массив элементов N//количество элементов в массиве passes = log2(N); while (passes >= 1) do increment = 2^(passes-1) – 1; for start = 1 to increment do InsertSort(list, N, start, increment)//сортировка полученного набора методом вставки end for; end while. 2. Оценка эффективности. В худшем случае: Code: T(n) = O(N^(3/2)) 3. Вывод. Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ: -отсутствие потребности в памяти под стек -отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(N^2), что хуже, чем худшее гарантированное время для сортировки Шелла Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов. (с) Wikipedia
как же вы надоели со своими квадратичными (да и вообще) сортировками! Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том. Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?
Данный топик создан с целью анализа алгоритмов вообще, а не только алгоритмов сортировок. Более сложные алгоритмы опираются на базовые (к коим относятся сортировки), поэтому считаю нужным рассмотреть базовую часть, чтобы перейти к более сложным обзорам. Не каждый осилит «Кнута», потому что книга насыщена математическими выкладками. Чтобы сравнить два алгоритма и определить, какой лучше использовать в нужном случае не обязательно «копаться» в лишнем материале. Достаточно разложить свой алгоритм на базовые алгоритмы и, проанализировав каждую часть, сделать вывод в общих чертах. Средние оценки у Кнута А если серьезно: большинство из рассмотренных на данный момент алгоритмов сортировок имеют оценку в среднем случае эквивалентную худшему случаю. Иначе – я уточняю. P.S. Спасибо за замечания.
>>книга насыщена математическими выкладками А что же такое "анализ алгоритмов" без математики? и не надо аппелировать к термину "класс задач" - у него немного другой смысл.
Согласен, выполнять анализ без математических методов трудно. Но здесь это не требуется - достаточно написать конечные результаты и сделать по ним выводы. Прошу Вас дать свой вариант определения "класса задач", чтобы заполнить пробел.
под классом задач обычно понимают http://ru.wikipedia.org/wiki/Класс_сложности >>достаточно написать конечные результаты и сделать по ним выводы. так напиши полезные результаты (а не пузырёк), и полные выводы. Например, сколько в среднем (по всем входным массивам) работает тот же пузырёк, и сколько обменов он совершает в среднем?
Из Википедии: Чтобы не быть голословным, объясните, где в своих постах я использовал данный термин не "по назначению". Я понимаю что метрика "среднего случая" для Вас крайне важна, но не настолько, чтобы она стояла по приоритетам выше "худший случай" и "лучший случай", которых вполне достаточно для сравнения алгоритмов по эффективности.
>>где в своих постах я использовал данный термин не "по назначению". Один алгоритм (или "способ решения") к классу задач нельзя применить. Класс задач лишь говорит, что например, заача решается за полиномиальное время. Но если за полиномиальное время можно и посадить картошку, и собрать яблоки - это не значит, что это делается одним и тем же способом. тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи". А, например, для похожих по смыслу задач проверки числа на простоту (невероятностного) и разложения на множители, первая имеет быстрое решение (логарифм числа в какой-то степени), а про вторую существование быстрого решения неизвестно. >>которых вполне достаточно для сравнения алгоритмов по эффективности. недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.
Для алгоритмов, уже описанных в этом топике, оценка среднего случая не так важна, тк в каждом из них она ближе к худшему случаю. А о сортировках из вашего примера (быстрой и слиянием) автор еще не упоминал, и я уверен, что когда он это сделает, то мы увидим оценку их временной сложности в среднем случае
Кнута не читал и пока не собираюсь. Эта статья интерсна, и чем больше в ней ставрительных характеристик тем лучше. Если будут выкладки из чего-либо кроме википедии - будет вообще perfect
Под классом задач тут понимается именно похожие по сложности задачи. Например схожие по размеру и степени упорядоченности массивы. Приведенные Вами алгоритмы сортировок я еще не успел рассмотреть. Повторюсь еще раз (и как заметил, Nikituki): в уже рассмотренных алгоритмах средний случай эквивалентен худшему. Ваше замечание я учту в дальнейших обзорах и средний случай буду рассматривать отдельно. Будет еще замечательней, если другие также будут выкладывать свои алгоритмы (не только базовые, коих хватает в Википедии) с их обзорами.
Циклический сдвиг элементов массива вправо на k позиций Ну чтож, попробую, мб кому-нибудь пригодится=) Циклический сдвиг элементов массива вправо на k позиций 1) Код: Code: template <typename MassiveType> void Shift(MassiveType *Massive, int MassiveLen, int k) { Reverse(Massive,0,MassiveLen-1); //разворачиваем массив Reverse(Massive,0,k-1); //разворачиваем первые к элементов Reverse(Massive,k,MassiveLen-1); //разворачиваем последние n-k эллементов } template <typename MassiveType> void Reverse(MassiveType *Massive, int StartElem, int FinishElem) { int i; MassiveType tresh; for (i=0;i<=(FinishElem-StartElem)/2;i++) { tresh=Massive[StartElem+i]; Massive[StartElem+i]=Massive[FinishElem-i]; Massive[FinishElem-i]=tresh; } } 2) Особенности: Не используется выделение больших объемов дополнительной памяти. 3) Временная сложность: Во всех случаях Т(n) = О(N)
