Просмотр полной версии : Оценка эффективности и быстродействия различных алгоритмов.
c0n Difesa
11.10.2009, 22:03
Существует множество способов решения определенной задачи (класса задач). Это множество порождает обилие алгоритмов, которые ее решают. Однако из этого набора алгоритмов можно выбрать те, которые справляются с поставленной задачей (классом задач) быстрее остальных, используя меньше ресурсов процессора и /или оперативной памяти.
Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения. Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным.
В качестве примера рассмотрим алгоритм сортировки массива методом вставки. Помимо этого я покажу как лучше оформлять сообщение, содержащее обзор алгоритма.
Сортировка массива методом вставки.
1. Псевдокод (справка: _http://ru.wikipedia.org/wiki/Псевдокод_(язык_описания_ал горитмов)), описывающий рассматриваемый алгоритм.
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, тогда временная сложность определяется следующим образом:
T(N) = C1 * N1 * C2 * N2 ~= С1 * С2 * (N^2) = O (N^2).
Скорость определяется элементом, стоящим в скобках.
Применим формулу к рассматриваемому алгоритму.
В лучшем случае (когда элементы массива уже упорядочены: [1, 2, 3, 4]):
T(N) = O (N).
В худшем случае (все элементы массива расположены в обратном порядке: [4, 3, 2, 1]):
T(N) = O ((N^2)/4).
3. Вывод.
Алгоритм сортировки методом вставки является наиболее быстродейственным для небольших массивов, с высокой степенью начальной упорядоченности.
Сортировка массива методом перестановки.
Дан массив из n чисел, отсортировать его по возврастанию.
Решение:
Будем генерировать все возможные перестановки из n элементов.
Среди всех возможных перестановок из n эл., существует такая в которой элементы расставлены в неубывающем порядке.
Завершаем алгоритм.
Временная сложность. В худшем случае требуется перебрать n! перестановок.
Вывод.
Более неэффективного алгоритма сортировки не существует.
-----------------------
2ErrorNeo Предложенный тобой алгоритм не решает задачу сортировки массива, т.к. он не всюду применим(он может не отсортировать данный массив за конечное время, т.е. мы не узнаем работает алгоритм или нет =) )
ErrorNeo
12.10.2009, 00:39
Более неэффективного алгоритма сортировки не существует.существует.
можно генерировать рандомные варианты перестановок из n эл. до тех пор, пока массив не окажется упорядоченным.
Если повезет - такой метод перестановки отработает всю сортировку за 1 перестановку. Если нет- решение может занять намного дольше твоего метода, т.к. каждая новая попытка в данном случае не увеличивает вероятности "успешного попадания".
А вообще самый быстрый из существующих методов сортировки массивов называется "quicksort"
http://ru.wikipedia.org/wiki/Быстрая_сортировка
метод описанный в первом посте - http://ru.wikipedia.org/wiki/Сортировка_вставками
Nikituki
12.10.2009, 23:43
А вообще самый быстрый из существующих методов сортировки массивов называется "quicksort"
http://ru.wikipedia.org/wiki/Быстрая_сортировка
Не соглашусь... У быстрой сортировки в худшем случае O(N^2), а в среднем O(N*log N).
У пирамидальной сортировки в любом случае (тоесть и в лучшем, и в худшем, и в среднем) O(N*log N).
Так же существует еще и поразрядная сортировка, которая вообще линейна...
c0n Difesa
17.10.2009, 12:50
1. Псевдокод.
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. Оценка временной сложности.
В лучшем случае (все элементы уже упорядоченны):
T(n) = O(N)
В худшем случае (элементы расположены в обратном порядке):
T(n) = (N - 1) + (N - 2) + ... + 1= O(N^2)
3. Вывод.
Простой алгоритм сортировки, эффективный для небольших массивов, однако, прост для понимания и легок для реализации.
c0n Difesa
17.10.2009, 13:05
1. Псевдокод
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 элементов имеет время выполнения в худшем, среднем и лучшем случае:
T(n) = O(N^2)
(c) Wikipedia
3. Вывод.
Неустойчивый алгоритм сортировки, обладающий одинаковым временем сортировки для небольших массивов разной степени упорядоченности, что делает его наиболее универсальным в своем классе.
c0n Difesa
18.10.2009, 14:40
1. Псевдокод.
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. Оценка эффективности.
В худшем случае:
T(n) = O(N^(3/2))
3. Вывод.
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
-отсутствие потребности в памяти под стек
-отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(N^2), что хуже, чем худшее гарантированное время для сортировки Шелла
Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов. (с) Wikipedia
как же вы надоели со своими квадратичными (да и вообще) сортировками!
Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том.
Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?
c0n Difesa
18.10.2009, 20:57
как же вы надоели со своими квадратичными (да и вообще) сортировками!
Данный топик создан с целью анализа алгоритмов вообще, а не только алгоритмов сортировок. Более сложные алгоритмы опираются на базовые (к коим относятся сортировки), поэтому считаю нужным рассмотреть базовую часть, чтобы перейти к более сложным обзорам.
Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том.
Не каждый осилит «Кнута», потому что книга насыщена математическими выкладками. Чтобы сравнить два алгоритма и определить, какой лучше использовать в нужном случае не обязательно «копаться» в лишнем материале. Достаточно разложить свой алгоритм на базовые алгоритмы и, проанализировав каждую часть, сделать вывод в общих чертах.
Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?
Средние оценки у Кнута ;) А если серьезно: большинство из рассмотренных на данный момент алгоритмов сортировок имеют оценку в среднем случае эквивалентную худшему случаю. Иначе – я уточняю.
P.S. Спасибо за замечания.
>>книга насыщена математическими выкладками
А что же такое "анализ алгоритмов" без математики?
и не надо аппелировать к термину "класс задач" - у него немного другой смысл.
c0n Difesa
18.10.2009, 21:40
>>книга насыщена математическими выкладками
А что же такое "анализ алгоритмов" без математики?
и не надо аппелировать к термину "класс задач" - у него немного другой смысл.
Согласен, выполнять анализ без математических методов трудно. Но здесь это не требуется - достаточно написать конечные результаты и сделать по ним выводы.
Прошу Вас дать свой вариант определения "класса задач", чтобы заполнить пробел.
BrainDeaD
18.10.2009, 22:35
"Аппелировать" - всмысле использовать?
Аппелировать = обращаться))
под классом задач обычно понимают http://ru.wikipedia.org/wiki/Класс_сложности
>>достаточно написать конечные результаты и сделать по ним выводы.
так напиши полезные результаты (а не пузырёк), и полные выводы. Например, сколько в среднем (по всем входным массивам) работает тот же пузырёк, и сколько обменов он совершает в среднем?
c0n Difesa
18.10.2009, 23:19
под классом задач обычно понимают http://ru.wikipedia.org/wiki/Класс_сложности
>>достаточно написать конечные результаты и сделать по ним выводы.
так напиши полезные результаты (а не пузырёк), и полные выводы. Например, сколько в среднем (по всем входным массивам) работает тот же пузырёк, и сколько обменов он совершает в среднем?
Из Википедии:
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления.
Чтобы не быть голословным, объясните, где в своих постах я использовал данный термин не "по назначению".
Я понимаю что метрика "среднего случая" для Вас крайне важна, но не настолько, чтобы она стояла по приоритетам выше "худший случай" и "лучший случай", которых вполне достаточно для сравнения алгоритмов по эффективности.
>>где в своих постах я использовал данный термин не "по назначению".
Существует множество способов решения определенной задачи (класса задач). Это множество порождает обилие алгоритмов, которые ее решают. Однако из этого набора алгоритмов можно выбрать те, которые справляются с поставленной задачей (классом задач) быстрее остальных, используя меньше ресурсов процессора и /или оперативной памяти.
Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения. Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным.
Один алгоритм (или "способ решения") к классу задач нельзя применить. Класс задач лишь говорит, что например, заача решается за полиномиальное время. Но если за полиномиальное время можно и посадить картошку, и собрать яблоки - это не значит, что это делается одним и тем же способом.
тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи". А, например, для похожих по смыслу задач проверки числа на простоту (невероятностного) и разложения на множители, первая имеет быстрое решение (логарифм числа в какой-то степени), а про вторую существование быстрого решения неизвестно.
>>которых вполне достаточно для сравнения алгоритмов по эффективности.
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.
Nikituki
19.10.2009, 14:08
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.
Для алгоритмов, уже описанных в этом топике, оценка среднего случая не так важна, тк в каждом из них она ближе к худшему случаю.
А о сортировках из вашего примера (быстрой и слиянием) автор еще не упоминал, и я уверен, что когда он это сделает, то мы увидим оценку их временной сложности в среднем случае ;)
ErrorNeo
19.10.2009, 14:34
Кнута не читал и пока не собираюсь.
Эта статья интерсна, и чем больше в ней ставрительных характеристик тем лучше.
Если будут выкладки из чего-либо кроме википедии - будет вообще perfect;)
c0n Difesa
19.10.2009, 14:47
тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи"
Под классом задач тут понимается именно похожие по сложности задачи. Например схожие по размеру и степени упорядоченности массивы.
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ?
Приведенные Вами алгоритмы сортировок я еще не успел рассмотреть. Повторюсь еще раз (и как заметил, Nikituki): в уже рассмотренных алгоритмах средний случай эквивалентен худшему. Ваше замечание я учту в дальнейших обзорах и средний случай буду рассматривать отдельно.
Кнута не читал и пока не собираюсь.
Эта статья интерсна, и чем больше в ней ставрительных характеристик тем лучше.
Если будут выкладки из чего-либо кроме википедии - будет вообще perfect
Будет еще замечательней, если другие также будут выкладывать свои алгоритмы (не только базовые, коих хватает в Википедии) с их обзорами. ;)
Nikituki
19.10.2009, 15:21
Будет еще замечательней, если другие также будут выкладывать свои алгоритмы (не только базовые, коих хватает в Википедии) с их обзорами. ;)
Ну чтож, попробую, мб кому-нибудь пригодится=)
Циклический сдвиг элементов массива вправо на k позиций
1) Код:
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)
vBulletin® v3.8.14, Copyright ©2000-2026, vBulletin Solutions, Inc. Перевод: zCarot