Форум АНТИЧАТ - Оценка эффективности и быстродействия различных алгоритмов.

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)

- С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)

- - Оценка эффективности и быстродействия различных алгоритмов. (https://forum.antichat.xyz/showthread.php?t=147554)

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. Вывод.

Алгоритм сортировки методом вставки является наиболее быстродейственным для небольших массивов, с высокой степенью начальной упорядоченности.

Irdis

12.10.2009 00:15

Сортировка массива методом перестановки.

Дан массив из n чисел, отсортировать его по возврастанию.
Решение:
Будем генерировать все возможные перестановки из n элементов.
Среди всех возможных перестановок из n эл., существует такая в которой элементы расставлены в неубывающем порядке.
Завершаем алгоритм.

Временная сложность. В худшем случае требуется перебрать n! перестановок.

Вывод.
Более неэффективного алгоритма сортировки не существует.
-----------------------
2ErrorNeo Предложенный тобой алгоритм не решает задачу сортировки массива, т.к. он не всюду применим(он может не отсортировать данный массив за конечное время, т.е. мы не узнаем работает алгоритм или нет =) )

ErrorNeo

12.10.2009 00:39

Цитата:

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

Более неэффективного алгоритма сортировки не существует.

существует.
можно генерировать рандомные варианты перестановок из n эл. до тех пор, пока массив не окажется упорядоченным.
Если повезет - такой метод перестановки отработает всю сортировку за 1 перестановку. Если нет- решение может занять намного дольше твоего метода, т.к. каждая новая попытка в данном случае не увеличивает вероятности "успешного попадания".

А вообще самый быстрый из существующих методов сортировки массивов называется "quicksort"
http://ru.wikipedia.org/wiki/Быстрая_сортировка

метод описанный в первом посте - http://ru.wikipedia.org/wiki/Сортировка_вставками

Nikituki

12.10.2009 23:43

Цитата:

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

А вообще самый быстрый из существующих методов сортировки массивов называется "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

desTiny

18.10.2009 20:28

как же вы надоели со своими квадратичными (да и вообще) сортировками!
Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том.

Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?

c0n Difesa

18.10.2009 20:57

Цитата:

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

как же вы надоели со своими квадратичными (да и вообще) сортировками!

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

Цитата:

Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том.

Не каждый осилит «Кнута», потому что книга насыщена математическими выкладками. Чтобы сравнить два алгоритма и определить, какой лучше использовать в нужном случае не обязательно «копаться» в лишнем материале. Достаточно разложить свой алгоритм на базовые алгоритмы и, проанализировав каждую часть, сделать вывод в общих чертах.

Цитата:

Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?

Средние оценки у Кнута ;) А если серьезно: большинство из рассмотренных на данный момент алгоритмов сортировок имеют оценку в среднем случае эквивалентную худшему случаю. Иначе – я уточняю.

P.S. Спасибо за замечания.

desTiny

18.10.2009 21:03

>>книга насыщена математическими выкладками
А что же такое "анализ алгоритмов" без математики?

и не надо аппелировать к термину "класс задач" - у него немного другой смысл.

c0n Difesa

18.10.2009 21:40

Цитата:

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

Согласен, выполнять анализ без математических методов трудно. Но здесь это не требуется - достаточно написать конечные результаты и сделать по ним выводы.

Прошу Вас дать свой вариант определения "класса задач", чтобы заполнить пробел.

BrainDeaD

18.10.2009 22:35

Цитата:

Сообщение от c0n Difesa

"Аппелировать" - всмысле использовать?

Аппелировать = обращаться))

desTiny

18.10.2009 23:07

под классом задач обычно понимают http://ru.wikipedia.org/wiki/Класс_сложности

>>достаточно написать конечные результаты и сделать по ним выводы.
так напиши полезные результаты (а не пузырёк), и полные выводы. Например, сколько в среднем (по всем входным массивам) работает тот же пузырёк, и сколько обменов он совершает в среднем?

c0n Difesa

18.10.2009 23:19

Цитата:

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

Из Википедии:

Цитата:

В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления.

Чтобы не быть голословным, объясните, где в своих постах я использовал данный термин не "по назначению".

Я понимаю что метрика "среднего случая" для Вас крайне важна, но не настолько, чтобы она стояла по приоритетам выше "худший случай" и "лучший случай", которых вполне достаточно для сравнения алгоритмов по эффективности.

desTiny

18.10.2009 23:54

>>где в своих постах я использовал данный термин не "по назначению".

Цитата:

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

Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения. Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным.

Один алгоритм (или "способ решения") к классу задач нельзя применить. Класс задач лишь говорит, что например, заача решается за полиномиальное время. Но если за полиномиальное время можно и посадить картошку, и собрать яблоки - это не значит, что это делается одним и тем же способом.

тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи". А, например, для похожих по смыслу задач проверки числа на простоту (невероятностного) и разложения на множители, первая имеет быстрое решение (логарифм числа в какой-то степени), а про вторую существование быстрого решения неизвестно.

>>которых вполне достаточно для сравнения алгоритмов по эффективности.
недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.

Nikituki

19.10.2009 14:08

Цитата:

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

недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ? А потому что, очень часто (читай - на случайном входе) быстродействие первого оказывается не хуже второго, а часто - лучше.

Для алгоритмов, уже описанных в этом топике, оценка среднего случая не так важна, тк в каждом из них она ближе к худшему случаю.
А о сортировках из вашего примера (быстрой и слиянием) автор еще не упоминал, и я уверен, что когда он это сделает, то мы увидим оценку их временной сложности в среднем случае ;)

ErrorNeo

19.10.2009 14:34

Кнута не читал и пока не собираюсь.
Эта статья интерсна, и чем больше в ней ставрительных характеристик тем лучше.
Если будут выкладки из чего-либо кроме википедии - будет вообще perfect;)

c0n Difesa

19.10.2009 14:47

Цитата:

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

тут под классом задач, как я понимаю, имеется в виду "похожие по смыслу задачи"

Под классом задач тут понимается именно похожие по сложности задачи. Например схожие по размеру и степени упорядоченности массивы.

Цитата:

недостаточно. Вот почему, по-вашему, так часто пишут qsort, хотя худший случай это N^2, а не merge - с N log N ?

Приведенные Вами алгоритмы сортировок я еще не успел рассмотреть. Повторюсь еще раз (и как заметил, Nikituki): в уже рассмотренных алгоритмах средний случай эквивалентен худшему. Ваше замечание я учту в дальнейших обзорах и средний случай буду рассматривать отдельно.

Цитата:

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

Будет еще замечательней, если другие также будут выкладывать свои алгоритмы (не только базовые, коих хватает в Википедии) с их обзорами. ;)

Nikituki

19.10.2009 15:21

Циклический сдвиг элементов массива вправо на k позиций

Цитата:

Сообщение от c0n Difesa

Ну чтож, попробую, мб кому-нибудь пригодится=)

Циклический сдвиг элементов массива вправо на 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)

Время: 02:50