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

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

11.10.2009, 22:03

c0n Difesa

Участник форума

Регистрация: 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]):

Код:

T(N) = O (N).

В худшем случае (все элементы массива расположены в обратном порядке: [4, 3, 2, 1]):

Код:

T(N) = O ((N^2)/4).

3. Вывод.

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

Последний раз редактировалось c0n Difesa; 11.10.2009 в 22:15..

ANTICHAT — форум по информационной безопасности, OSINT и технологиям