Существует множество способов решения определенной задачи (класса задач). Это множество порождает обилие алгоритмов, которые ее решают. Однако из этого набора алгоритмов можно выбрать те, которые справляются с поставленной задачей (классом задач) быстрее остальных, используя меньше ресурсов процессора и /или оперативной памяти.
Цель данного топика: рассмотреть как можно больше алгоритмов, оценить их временную сложность и определить границы эффективного применения.
Границы эффективного применения – класс задач, для которого рассматриваемый алгоритм будет наиболее быстродейственным.
В качестве примера рассмотрим алгоритм сортировки массива
методом вставки. Помимо этого я покажу как
лучше оформлять сообщение, содержащее обзор алгоритма.
Сортировка массива методом вставки.
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. Вывод.
Алгоритм сортировки методом вставки является наиболее быстродейственным для небольших массивов, с высокой степенью начальной упорядоченности.