Эффективность алгоритма в разных случаях

Мы определили, что имеет смысл оценивать эффективность алгоритма как функцию от некоторого параметра n, связанного с размером входных данных. Однако существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от особенностей конкретных входных данных. В качестве примера рассмотрим задачу последовательного поиска. Она решается с помощью довольно простого алгоритма, который выполняет поиск заданного элемента (ключа поиска К) в списке, состоящем из n элементов, путем последовательного сравнения ключа К с каждым из элементов списка. Работа алгоритма завершается, либо когда заданный ключ найден, либо когда весь список исчерпан. Ниже этот алгоритм описан на псевдокоде. В нем для простоты полагается, что список задан в виде массива чисел. (Кроме того, предполагается, что второе условие А[i]¹ К не будет проверяться в случае, если не выполняется первое условие, в котором проверяется, не выходит ли индекс массива за его верхнюю границу.)

Совершенно очевидно, что время работы этого алгоритма может отличаться в очень широких пределах для одного и того же списка размера n. В наихудшем случае, т.е. когда в списке нет искомого элемента либо когда искомый элемент расположен в списке последним, в алгоритме будет выполнено наибольшее количество операций сравнения ключа со всеми n элементами списка: C_worst (n) = n. Под эффективностью алгоритма в наихудшем случае {worst-case efficiency) подразумевают его эффективность для наихудшей совокупности входных данных размером n, т.е. для такой совокупности входных данных размером n среди всех возможных, для которой время работы алгоритма будет наибольшим. Способ определения эффективности алгоритма для наихудшего случая в принципе несложен: нужно проанализировать алгоритм и выяснить, для каких из возможных комбинаций входных данных размером n значение числа основных операций алгоритма С (n) будет максимальным, а затем вычислить значение C_worst(n) для наихудшего случая.

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

Под эффективностью алгоритма в наилучшем случае {best-case efficiency) подразумевают его эффективность для наилучшей совокупности входных данных размером n, т.е. для такой совокупности входных данных размером n среди всех возможных, для которой время работы алгоритма будет наименьшим.

Соответственно, эффективность алгоритма для наилучшего случая можно проанализировать следующим образом. Сначала нужно определить, для каких из возможных комбинаций входных данных размером n значение числа основных операций алгоритма С(n) будет наименьшим. (Обратите внимание, что наилучший случай вовсе не означает случай, когда вводится минимальное количество данных. Он означает комбинацию входных данных размером n, при обработке которых алгоритм будет работать быстрее всего.). Затем необходимо определить само значение C_best (n) для такого случая. Например, для алгоритма последовательного поиска наилучшим случаем входных данных будет такой список размером n, первый элемент которого равен ключу поиска К. Поэтому для него C_best (n) = 1. Анализ эффективности алгоритма для наилучшего случая не так важен, как для наихудшего случая, хотя его нельзя назвать совсем уж бесполезным. При анализе алгоритма не стоит полагаться на то, что обрабатываемые им данные будут соответствовать наилучшему случаю. Тем не менее нужно учитывать тот факт, что для некоторых алгоритмов их высокое быстродействие для наилучшего случая сохраняется и для случаев близких к наилучшему. Например, существует алгоритм сортировки методом вставок, для которого наилучший случай входных данных соответствует заранее отсортированному массиву. При этом скорость работы такого алгоритма будет наибольшей. Причем она лишь ненамного ухудшается в случае, если входной массив почти отсортирован. Следовательно, такой алгоритм очень хорошо подойдет для случаев, когда приходится иметь дело с почти отсортированными массивами. Ну и конечно же, если эффективность алгоритма для наилучшего случая является неудовлетворительной, не имеет смысла продолжать его дальнейший анализ.

Как бы там ни было, из данного описания уже должно быть понятно, что на основании информации, полученной в результате анализа алгоритма для наилучшего и наихудшего случаев, нельзя сделать вывод о том, как поведет себя алгоритм при обработке типовых или случайно заданных входных данных. Чтобы получить подобную информацию, нужно выполнить анализ алгоритма для среднего случая (average-case efficiency). Для этого нужно сделать ряд предположений о совокупности входных данных размером n.

Продолжим рассмотрение алгоритма поиска методом последовательного перебора. Сделаем два стандартных предположения:

1. вероятность успешного поиска равна р, где 0£р £1;

2. вероятность первого совпадения ключа с i-м элементом списка одинакова для любого i.

Исходя из этих предположений можно вычислить среднее количество операций сравнения с ключом C_avg(n), как описано ниже. Если совпадение с ключом найдено, вероятность того, что это произошло именно на i-м элементе списка, равна р/n для любого i. При этом количество операций сравнения, выполняемых в алгоритме в подобном случае, очевидно и равно i. Если совпадение с ключом не найдено, количество операций сравнения равно n, а вероятность этого события равна (1 — р). Поэтому

Эта обобщенная формула позволяет ответить на несколько вопросов. Например, если р = 1 (т.е. искомый элемент, равный ключу, точно присутствует в списке и поэтому будет найден), среднее количество операций сравнения при поиске методом последовательного перебора будет равно (n + 1)/2.

Другими словами, в среднем, в алгоритме проверяется приблизительно половина элементов списка. Если р = 0 (т.е. искомого элемента в списке нет), среднее количество операций сравнения будет равно n, поскольку при этом в алгоритме проверяются все n элементов списка.

Как видно из этого простого примера, определение эффективности алгоритма для среднего случая куда более трудная задача, чем для наихудшего и наилучшего случаев. При использовании прямого метода для решения этой задачи, необходимо разбить всю совокупность экземпляров входных данных размером n на несколько групп так, чтобы для каждой группы число основных операций, выполняемых алгоритмом, было одинаково. Затем нужно найти или придумать функцию распределения вероятностей для входных данных и с ее помощью вычислить ожидаемое значение количества основных операций алгоритма. Технически реализовать этот план не составит большого труда, хотя проверить вероятностные предпосылки, лежащие в его основе, обычно очень тяжело. Поэтому для простоты, когда речь будет заходить об анализе эффективности для среднего случая, мы чаще всего будем приводить уже готовые результаты для обсуждаемого алгоритма. Таким образом, информация об эффективности алгоритма для среднего случая позволяет принять правильное решение и не упустить много важных алгоритмов. Наконец, из приведенного выше описания понятно, что эффективность алгоритма для среднего случая нельзя получить, усреднив его эффективности для наихудшего и наилучшего случаев.

Существует еще один вид эффективности, называемый амортизированной эффективностью {amortized efficiency). Она предназначена не столько для анализа общего времени выполнения алгоритма, сколько для анализа последовательности операций, выполняемых над одной и той же структурой данных. Бывает так, что одна из операций алгоритма может оказаться слишком продолжительной, но общее время выполнения последовательности из n таких операций будет значительно меньше, чем его оценка, выполненная для наихудшего случая, равная произведению максимального времени выполнения этой операции на число таких операций n. Поэтому мы можем разделить (или "амортизировать") высокую стоимость выполнения алгоритма для наихудшего случая на всю последовательность выполняемых операций по аналогии с тем, как в экономике разносят стоимость дорогостоящего оборудования на весь период его эксплуатации. Этот нетривиальный подход был предложен американским кибернетиком Робертом Таржаном. Он использовал его наряду с другими методами для исследования интересного варианта классического двоичного дерева поиска.

Асимптотические обозначения и основные классы эффективности

Как отмечалось при изложении основ анализа эффективности алгоритмов, основное внимание было сосредоточено на порядке роста количества базовых операций алгоритма, который мы использовали в качестве основного критерия эффективности алгоритма. Для того чтобы можно было сравнивать между собой эти порядки роста и классифицировать их, ученые ввели три условных обозначения: О (прописная "О"), Q (прописная греческая "тета") и W (прописная греческая "омега"). Для начала дадим нестрогое описание этих понятий, а затем, рассмотрев несколько примеров, приведем их строгое определение.

В приведенном ниже описании t (n) и g(n) могут быть любыми неотрицательными функциями, определенными на множестве натуральных чисел. Через t(n) мы обозначили время выполнения алгоритма. Обычно оно выражается в виде числа основных операций алгоритма, обозначаемых через С(n). Под g(n) мы будем понимать некоторую простую функцию, с которой будет проводиться сравнение количества операций. Говоря нестрого, обозначение О (g(n)) — это множество всех функций, порядок роста которых при достаточно больших n не превышает (т.е. меньше или равен) некоторую константу, умноженную на значение функции g(n). Вот несколько примеров — все приведенные ниже утверждения справедливы:

nÎО(n²), 100n + 5 ÎО(n²), n(n-1)/2 ÎО(n²).

В самом деле, первые две функции линейны, поэтому их порядок роста заведомо меньше, чем g(n) = n². Последняя функция является квадратичной, поэтому ее порядок роста такой же, как у функции n². С другой стороны, n³ Ï О(n²), 0.00001n³ Ï О(n²), n⁴ + n + 1 Ï О(n²). В самом деле, обе функции n³ и 0.00001n³ являются кубическими, поэтому имеют более высокий порядок роста, чем функция n². Те же рассуждения справедливы и для полинома четвертой степени n⁴ +n + 1. Второе обозначение, W (g(n)), — это множество всех функций, порядок роста которых при достаточно больших n не меньше (т.е. больше или равен) некоторой константы, умноженной на значение функции g(n). Например: n³ÎW (n²); n(n-1)/2ÎW (n²); 100n + 5ÏW (n²)

Наконец, обозначение Q(g(n)) — это множество всех функций, порядок роста которых при достаточно больших n равен некоторой константе, умноженной на значение функции g(n). Таким образом, любая квадратичная функция an² + bn +с при а > 0 принадлежит множеству Q(n²). Кроме того, среди бесконечного количества других функций множеству Q(n²) принадлежат также функции n² + sinn и n²+ log n.

Дата добавления: 2014-01-20