Анализ алгоритма

image
Что такое анализ?
Анализируя алгоритм, можно получить представление о том, сколько времени займет решение данной задачи при помощи данного алгоритма. Одну и ту же задачу можно решить с помощью различных алгоритмов. Анализ алгоритмов дает нам инструмент для выбора алгоритма.
Результат анализа алгоритмов — не формула для точного количества секунд или компьютерных циклов, которые потребует конкретный алгоритм. Нужно понимать, что разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим.


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

Наилучший случай

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

Наихудший случай

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

Средний случай

Анализ среднего случая является самым сложным, поскольку он требует учета множества разнообразных деталей. В основе анализа лежит определение различных групп, на которые следует разбить возможные входные наборы данных. На втором шаге определяется вероятность, с которой входной набор данных принадлежит каждой группе. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует подразбить. Среднее время работы вычисляется по формуле
image

где через n обозначен размер входных данных, через m — число групп. через pi — вероятность того, что входные данные принадлежат группе с номером i, а через ti — время, необходимое алгоритму для обработки данных из группы с номером i.

В большинстве случаев мы будем предполагать, что вероятности попадания входных данных в каждую из групп одинаковы. Другими словами, если групп пять, то вероятность попасть в первую группу такая же, как вероятность попасть во вторую, и т.д., то есть вероятность
попасть в каждую группу равна 0.2. В этом случае среднее время работы можно либо оценить по предыдущей формуле, либо воспользоваться эквивалентной ей формулой
image

Нижние границы. Дерево решений.
Алгоритм является оптимальным, если любой любой другой алгоритм, решающий данную задачу, работает не быстрее данного. Как узнать оптимальность алгоритма? Для этого мы должны знать минимальное количество операций, необходимое для решения поставленной задачи, которое называется нижней границей. Но для этого нам нужно изучать именно ЗАДАЧУ, а не конкретный алгоритм!
Как пример, рассмотрим анализ процесса сортировки списка из 3 чисел, воспользовавшись бинарным деревом. Такое дерево называется деревом решений.
image

Самый длинный путь в данном дереве соответствует наихудшему случаю и наоборот, кратчайший — наилучшему. Средний случай описывается частным от деления числа ребер в дереве на число листов.
Для перестановки 2-х элементов мы имеем 1лист, для N эл-тов, по правилам комбинаторики, N! листов. Число листов на уровне K равно 2k-1, поэтому в нашем дереве решений буде L -уровней, где L — наименьшее целое число, для которого N! ≤ 2L-1. Логарифмируя, получим
image
image
image
В конечном итоге, получаем:
image
Вот мы и узнали, что любой алгоритм сортировки, порядка О(NlgN) является наилучшим и его можно считать оптимальным. Более того, из этого исследования вытекает, что алгоритм, решающий задачу сортировки быстрее О(NlgN) операций, не может работать правильно!

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 7

    +8
    Как-то коротко и поверхностно. Тема-то богатая. Понятно, что текст расчитан на тех, кто не в курсе, но и для них мало сказано.
      0
      Согласен. Но от богатства темы и сложности описания возникают. Хотелось бы упомянуть начинающим, но интересующимся, про порядки роста. А в целом, обычно, анализ проводится по конкретному алгоритму или классу алгоритмов.
      0
      Очень поверхностно и ничего не понятно человеку, который очень слабо в теме.

      Кстати сказать, третья, кажется, глава «Идеального кода» (под ред. Энди Орама и Грега Уилсона) очень доходчиво (для новичка) рассматривает вопрос аналза алгоритмов на примере quicksort.
        +1
        А уж если прочитать книгу за авторством Кормена, Лейзерсона, Ривеста… :)
          0
          Книга про построение и анализ алгоритмов прекрасна, но у нее есть один серьезный недостаток: она больше по математике :) Для программистов «старой закалки» это нормально, но не все современные программисты, увы, имеют хорошую подготовку. Джон Бенли же (именно он автор третьей главы) подходит к анализу алгоритма со стороны кода, последовательно подводя читателя к интуитивному пониманию математического формализма. Оба подхода, кстати сказать, эквивалентны, правда последний более многословен, зато понятен непосвященным.

          Я сейчас ни в коем случае не имею ввиду, что «программисту не надо знать математику». Тем не менее, фактом является то, что далеко не все программисты хорошо знают математику.
            +1
            Согласен, но дело не только во времени. Дело в разнице отраслей. Это также как и в инженерии: кто-то создает новые законы, материалы и т.д., а кто-то это все объединяет в новое устройство. Математика нужна тем, кто создаёт новые материалы, чтобы потом кто-то смог построить из них космический корабль. И тут вступает в силу банальная структура институтов, т.е. накопление знаний с основ, чтобы поняв их и придумать своё или улучшить существующее!

            Мне вот больше понравилось пытаться создать новые материалы, чем строить из таких кусочков бизнес кораблики. :)
        0
        Данный пример показался мне хорошим тем, что он доказал, что любой алгоритм сортировки, порядка О(NlgN) является наилучшим! И тем самым перечеркнул все сказочные помыслы на волшебство порядка О(N)! :)

        Only users with full accounts can post comments. Log in, please.