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

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

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

Оценка эффективности и быстродействия различных алгоритмов.

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

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

В качестве примера рассмотрим алгоритм сортировки массива методом вставки. Помимо этого я покажу как лучше оформлять сообщение, содержащее обзор алгоритма.

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

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 Предложенный тобой алгоритм не решает задачу сортировки массива, т.к. он не всюду применим(он может не отсортировать данный массив за конечное время, т.е. мы не узнаем работает алгоритм или нет =) )

Цитата:

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

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

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

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

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

Цитата:

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

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

Не соглашусь... У быстрой сортировки в худшем случае O(N^2), а в среднем O(N*log N).
У пирамидальной сортировки в любом случае (тоесть и в лучшем, и в худшем, и в среднем) O(N*log N).
Так же существует еще и поразрядная сортировка, которая вообще линейна...

Сортировка методом "пузырька".

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

Простой алгоритм сортировки, эффективный для небольших массивов, однако, прост для понимания и легок для реализации.

Сортировка простым выбором.

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

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

Сортировка Шелла.

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)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?

Цитата:

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

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

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

Цитата:

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

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

Цитата:

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

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

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

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

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