алгоритм

Введение в алгоритмы. Сложность алгоритма

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

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

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

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

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

Например, у нас есть алгоритм вычисления максимального элемента в массиве. Допустим, мы реализовали задачу следующим образом:

Код    
  1. int max = a[0];
  2.         for (int i = 0; i < n; i++) {//n - длина массива
  3.             if (a[i]>max)
  4.                 max = a[i];
  5.         }

Предположим, что наш процессор может выполнять следующие операции как одну команду:

  • Присвоение значения переменной;
  • Поиск значения определенного элемента в массиве;
  • Сравнение двух значений;
  • Увеличение значения;
  • Основные арифметические операции, такие как сложение и умножение.

Для чего мы делаем такое предположение? Когда мы будем анализировать этот фрагмент кода, нам будет нужно разбить его на простые инструкции. То есть те, которые могут быть выполнены непосредственно процессором — или близко к этому.

Давайте приступим.

Первая строчка кода: 

Код    
  1. int max = a[0];

Для этого требуются два действия: одно для поиска а [0] и второе для присвоения значения max (будем считать, что длина массива всегда больше 1). Эти два действия всегда требуются алгоритмом, независимо от значения длины массива. Код инициализации цикла for также должен всегда выполняться. Это дает нам еще два действия; присвоение и сравнение. 

Код    
  1. i = 0;
  2. i < n;

Эти строки будут выполняться перед первой итерацией цикла. После каждой итерации нам понадобятся еще два действия: инкремент i и сравнение, чтобы проверить, останемся ли мы в цикле:

Код    
  1. i++;
  2. i < n;

Таким образом, если мы игнорируем тело цикла, количество действий, которые необходимы этому алгоритму, равно 4 + 2n. То есть, 4 инструкции в начале цикла for и 2 команды в конце каждой итерации, из которых мы имеем n. Теперь мы можем определить математическую функцию f (n), которая, учитывая n, дает нам количество инструкций, которые необходимы алгоритму. Для пустого тела мы имеем f (n) = 4 + 2n. Но, это для наилучшего сценария. В теории алгоритмов принято, что, считая сложность алгоритма, нужно выбирать наиболее сложный сценарий.

Значит, нам нужно посчитать количество операций в теле цикла. Давайте сделаем и это.

Код    
  1. if (a[i]>max)

Мы уже умные и можем посчитать, что в этом выражении два действия. Но тело if может работать или не запускаться, в зависимости от того, какие значения массива на самом деле. Если случится так, что а [i]> = мах, мы запустим эти две дополнительные команды — поиск в массиве и присвоение: max = a[i].

Вот мы и пришли к тому месту, когда определить количество команд оказалось не так то просто. Ведь теперь результат зависит от того, какие данные придут к нам на вход. Например, для а = [1, 2, 3, 4] алгоритму потребуется больше инструкций, чем для а = [4, 3, 2, 1]. Тут нужно помнить правило наихудшего сценария: всегда считайте сложность алгоритма за наихудшим сценарием. Так Вы будете уверены, что он не отработает хуже, чем Вы предполагали.

Таким образом, в худшем случае у нас есть 4 действия для выполнения внутри тела for, поэтому мы имеем f (n) = 4 + 2n + 4n = 6n + 4. Эта функция f, заданная размером задачи n, дает нам число инструкций, которые понадобятся в худшем случае.

Теперь, когда мы написали нашу функцию, нужно отбросить все, что не входит в количество вхождений n. То есть, мы просто игнорируем все числа в функции (даже те, который умножаются на n) в виду их слабым влиянием на количество действий. Посудите сами: при n=5, значение функции будет 65+4=34; при n=100: 6100+4=604; n=10000: 6*10000+4=60004. Короче говоря основную массу операций делает величина n.

Хотя это может показаться нелогично, мы будем отбрасывать все аргументы, которые при росте n будут расти медленнее. Даже вот такое выражение: n^2 + 6n + 7 нужно «урезать» до n^2.

Поскольку мы можем отбросить все не нужные нам части выражения, довольно легко определить асимптотическое поведение функции и подсчет команд в программе. Фактически, любая программа, у которой нет каких-либо циклов, будет иметь f (n) = 1, так как количество необходимых ей инструкций — это просто константа. Если только это не рекурсия.

Любая программа с одним циклом, который идет от 1 до n, будет иметь f (n) = n, так как она будет выполнять постоянное количество действий перед циклом, постоянное количество инструкций после цикла и постоянное количество действий внутри цикла. Короче говоря: простые программы могут быть проанализированы путем подсчета вложенных циклов программы. Один цикл по n элементов дает f (n) = n. Цикл внутри цикла дает f (n) = n^2. Цикл внутри цикла внутри цикла дает f (n) = n^3.

Я не зря выделил слово «вложенных». Так как у нас в программе могут быть последовательные циклы, которые Вы можете перепутать с вложенными. Если идут несколько циклов друг за другом, то сложность не будет увеличиваться, с количеством циклов. Даже если у Вас в программе 4 цикла, которые идут друг за другом — сложность такого алгоритма нельзя назвать f (n) = n^4.

Вы возможно уже видели или еще увидите вот такой «О» или вот такой «Θ» символ отображения сложности алгоритмов. Читаются они соответственно: о и тета.

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

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

Эта статья является частичным переводом очень крутой и интересной статьи о алгоритмах, которая может Вас «просветить». Если английский позволяет — то читайте оригинал и наслаждайтесь.

Добавить комментарий