Antichat снова доступен.
Форум Antichat (Античат) возвращается и снова открыт для пользователей.
Здесь обсуждаются безопасность, программирование, технологии и многое другое.
Сообщество снова собирается вместе.
Новый адрес: forum.antichat.xyz
 |
|
Оценка эффективности и быстродействия различных алгоритмов. |
11.10.2009, 22:03
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Оценка эффективности и быстродействия различных алгоритмов.
Существует множество способов решения определенной задачи (класса задач). Это множество порождает обилие алгоритмов, которые ее решают. Однако из этого набора алгоритмов можно выбрать те, которые справляются с поставленной задачей (классом задач) быстрее остальных, используя меньше ресурсов процессора и /или оперативной памяти.
Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения. Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным.
В качестве примера рассмотрим алгоритм сортировки массива методом вставки. Помимо этого я покажу как лучше оформлять сообщение, содержащее обзор алгоритма.
Сортировка массива методом вставки.
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]):
В худшем случае (все элементы массива расположены в обратном порядке: [4, 3, 2, 1]):
3. Вывод.
Алгоритм сортировки методом вставки является наиболее быстродейственным для небольших массивов, с высокой степенью начальной упорядоченности.
Последний раз редактировалось c0n Difesa; 11.10.2009 в 22:15..
|
|
|
12.10.2009, 00:15
|
|
Участник форума
Регистрация: 06.02.2006
Сообщений: 177
Провел на форуме:
1576821
Репутация:
88
|
|
Сортировка массива методом перестановки. Дан массив из n чисел, отсортировать его по возврастанию.
Решение:
Будем генерировать все возможные перестановки из n элементов.
Среди всех возможных перестановок из n эл., существует такая в которой элементы расставлены в неубывающем порядке.
Завершаем алгоритм.
Временная сложность. В худшем случае требуется перебрать n! перестановок.
Вывод.
Более неэффективного алгоритма сортировки не существует.
-----------------------
2ErrorNeo Предложенный тобой алгоритм не решает задачу сортировки массива, т.к. он не всюду применим(он может не отсортировать данный массив за конечное время, т.е. мы не узнаем работает алгоритм или нет =) )
Последний раз редактировалось Irdis; 12.10.2009 в 04:26..
|
|
|
|
12.10.2009, 00:39
|
|
Moderator - Level 7
Регистрация: 02.05.2009
Сообщений: 894
Провел на форуме:
4297091
Репутация:
2261
|
|
Сообщение от Irdis
Более неэффективного алгоритма сортировки не существует.
существует.
можно генерировать рандомные варианты перестановок из n эл. до тех пор, пока массив не окажется упорядоченным.
Если повезет - такой метод перестановки отработает всю сортировку за 1 перестановку. Если нет- решение может занять намного дольше твоего метода, т.к. каждая новая попытка в данном случае не увеличивает вероятности "успешного попадания".
А вообще самый быстрый из существующих методов сортировки массивов называется "quicksort"
http://ru.wikipedia.org/wiki/Быстрая_сортировка
метод описанный в первом посте - http://ru.wikipedia.org/wiki/Сортировка_вставками
|
|
|
|
12.10.2009, 23:43
|
|
Новичок
Регистрация: 14.03.2009
Сообщений: 25
Провел на форуме:
72034
Репутация:
5
|
|
Сообщение от ErrorNeo
А вообще самый быстрый из существующих методов сортировки массивов называется "quicksort"
http://ru.wikipedia.org/wiki/Быстрая_сортировка
Не соглашусь... У быстрой сортировки в худшем случае O(N^2), а в среднем O(N*log N).
У пирамидальной сортировки в любом случае (тоесть и в лучшем, и в худшем, и в среднем) O(N*log N).
Так же существует еще и поразрядная сортировка, которая вообще линейна...
|
|
|
|
Сортировка методом "пузырька". |
17.10.2009, 12:50
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сортировка методом "пузырька".
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) = (N - 1) + (N - 2) + ... + 1= O(N^2)
3. Вывод.
Простой алгоритм сортировки, эффективный для небольших массивов, однако, прост для понимания и легок для реализации.
|
|
|
|
Сортировка простым выбором. |
17.10.2009, 13:05
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сортировка простым выбором.
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 элементов имеет время выполнения в худшем, среднем и лучшем случае:
(c) Wikipedia
3. Вывод.
Неустойчивый алгоритм сортировки, обладающий одинаковым временем сортировки для небольших массивов разной степени упорядоченности, что делает его наиболее универсальным в своем классе.
|
|
|
|
18.10.2009, 14:40
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сортировка Шелла.
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. Оценка эффективности.
В худшем случае:
3. Вывод.
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
-отсутствие потребности в памяти под стек
-отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(N^2), что хуже, чем худшее гарантированное время для сортировки Шелла
Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов. (с) Wikipedia
|
|
|
|
18.10.2009, 20:28
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
Провел на форуме:
3008839
Репутация:
1502
|
|
как же вы надоели со своими квадратичными (да и вообще) сортировками!
Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том.
Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
18.10.2009, 20:57
|
|
Участник форума
Регистрация: 01.01.2009
Сообщений: 144
Провел на форуме:
89680
Репутация:
154
|
|
Сообщение от desTiny
как же вы надоели со своими квадратичными (да и вообще) сортировками!
Данный топик создан с целью анализа алгоритмов вообще, а не только алгоритмов сортировок. Более сложные алгоритмы опираются на базовые (к коим относятся сортировки), поэтому считаю нужным рассмотреть базовую часть, чтобы перейти к более сложным обзорам.
Кому очень интересно узнать всё в детелях и подробностях, вникнуть во все реккуренты - добро пожаловать, у Кнута целый том.
Не каждый осилит «Кнута», потому что книга насыщена математическими выкладками. Чтобы сравнить два алгоритма и определить, какой лучше использовать в нужном случае не обязательно «копаться» в лишнем материале. Достаточно разложить свой алгоритм на базовые алгоритмы и, проанализировав каждую часть, сделать вывод в общих чертах.
Плюс жалкие намёки на оценку сложности. Ну в худшем случае O(g(n)). И что? Где средние оценки времени?? Где оценки, например, среднего количества обменов элементов?
Средние оценки у Кнута  А если серьезно: большинство из рассмотренных на данный момент алгоритмов сортировок имеют оценку в среднем случае эквивалентную худшему случаю. Иначе – я уточняю.
P.S. Спасибо за замечания.
|
|
|
|
18.10.2009, 21:03
|
|
Reservists Of Antichat - Level 6
Регистрация: 04.02.2007
Сообщений: 1,152
Провел на форуме:
3008839
Репутация:
1502
|
|
>>книга насыщена математическими выкладками
А что же такое "анализ алгоритмов" без математики?
и не надо аппелировать к термину "класс задач" - у него немного другой смысл.
__________________
Bedankt euch dafür bei euch selbst.
H_2(S^3/((z1, z2)~(exp(2pi*i/p)z1, exp(2pi*q*i/p)z2)))=Z/pZ
|
|
|
|
|
|
|
|
Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
|
|
|
|
Линейный вид
