Оценка сложности алгоритмов

    Не так давно мне предложили вести курс основ теории алгоритмов в одном московском лицее. Я, конечно, с удовольствием согласился. В понедельник была первая лекция на которой я постарался объяснить ребятам методы оценки сложности алгоритмов. Я думаю, что некоторым читателям Хабра эта информация тоже может оказаться полезной, или по крайней мере интересной.
    Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

    Память или время


    Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
    Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
    Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
    Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.
    Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

    Оценка порядка


    При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
    В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.
    for i:=1 to N do
    begin
    max:=A[i,1];
    for j:=1 to N do
    begin
    if A[i,j]>max then
    max:=A[i,j]
    end;
    writeln(max);
    end;

    В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2).
    Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
    При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

    Определение сложности


    Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов.
    Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
    В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
    procedure Slow;
    var
    i,j,k: integer;
    begin
    for i:=1 to N do
    for j:=1 to N do
    for k:=1 to N do
    {какое-то действие}
    end;
    procedure Fast;
    var
    i,j: integer;
    begin
    for i:=1 to N do
    for j:=1 to N do
    Slow;
    end;
    procedure Both;
    begin
    Fast;
    end;

    Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5).
    Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=O(N^3). Следующий фрагмент имеет именно такую сложность:
    procedure Slow;
    var
    i,j,k: integer;
    begin
    for i:=1 to N do
    for j:=1 to N do
    for k:=1 to N do
    {какое-то действие}
    end;
    procedure Fast;
    var
    i,j: integer;
    begin
    for i:=1 to N do
    for j:=1 to N do
    {какое-то действие}
    end;
    procedure Both;
    begin
    Fast;
    Slow;
    end;

    Сложность рекурсивных алгоритмов

    Простая рекурсия

    Напомним, что рекурсивными процедурами называются процедуры, которые вызывают сами себя. Их сложность определить довольно тяжело. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций рекурсии. Рекурсивная процедура может выглядеть достаточно простой, но она может серьёзно усложнить программу, многократно вызывая себя.
    Рассмотрим рекурсивную реализацию вычисления факториала:
    function Factorial(n: Word): integer;
    begin
    if n > 1 then
    Factorial:=n*Factorial(n-1)
    else
    Factorial:=1;
    end;

    Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).
    Многократная рекурсия

    Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать, кроме того, они могут сделать алгоритм гораздо сложнее.
    Рассмотрим такую процедуру:
    procedure DoubleRecursive(N: integer);
    begin
    if N>0 then
    begin
    DoubleRecursive(N-1);
    DoubleRecursive(N-1);
    end;
    end;

    Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2^(N+1)-1)=O(2^N). Всегда надо помнить, что анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.
    Объёмная сложность рекурсивных алгоритмов

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

    Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.
    function Locate(data: integer): integer;
    var
    i: integer;
    fl: boolean;
    begin
    fl:=false; i:=1;
    while (not fl) and (i<=N) do
    begin
    if A[i]=data then
    fl:=true
    else
    i:=i+1;
    end;
    if not fl then
    i:=0;
    Locate:=I;
    end;

    Если искомый элемент находится в конце списка, то программе придётся выполнить N шагов. В таком случае сложность алгоритма составит O(N). В этом наихудшем случае время работы алгоритма будем максимальным.
    С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).
    Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).
    В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.
    Общие функции оценки сложности

    Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
    1. C – константа
    2. log(log(N))
    3. log(N)
    4. N^C, 0<C<1
    5. N
    6. N*log(N)
    7. N^C, C>1
    8. C^N, C>1
    9. N!
    Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
    Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
    Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
    В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 66
      +1
      Разве учащиеся лицея не знают что такое предел?
        +2
        В 10-х классах — нет. В 11 пока нет.
          +1
          тогда ладно. сам пытался рассказывать интуитивную оценку сложности алгоритмов — без пределов это очень поверхностно осознается; казалось бы в простейших случаях ребята все понимают, но в более сложных рассуждая «по аналогии» совершают ошибки. у классов с базовым представлением о мат. анализе проблем не возникало.
            +2
            Если уж товарищи заинтересовались алгоритмами, то можно было бы вкратце и объяснить, что такое предел. Благо, это несложно, но сугубо необходимо для дальнейшего роста.
              0
              тогда уж может вы расскажите? :)
                +1
                На этот счет есть полно хороших книжек (к примеру, Introduction to Algorithms Кормена и компании). Читайте, и да будет вам просветление.
                  +2
                  очень просто отсылать к книге, не попробовав объяснить на пальцах самому
                    +1
                    Я сам не пробовал школьникам объяснять, что такое предел, но мне в десятом классе это прекрасно объяснили абсолютно строго (нет, я не учился в мат. классе).
                    +2
                    Назвался груздем — полезай в кузов.
                  +2
                  Успеют они это выучить, моё дело дать самые основы.
                    +2
                    Не надо основы подменять словоблудием.

                    > Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

                    А вас на этом месте никто не прервал вопросом «как определить формально скорость роста функции»?
                      +3
                      Кстати, конкретно для обозначения O(f(n)) никакие пределы не нужны. Достаточно ограниченности сверху. Это уж точно можно объяснить.
                    0
                    учился в физ-мат школе, но в 10 классе предел понимается на отличненько. а как проходят производные без предела?
                  –10
                  Почитал ради интереса «А как сейчас преподают сложность алгоритма?».
                  Лицей, Паскаль — в принципе для школьников самое то.

                  А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?

                    +8
                    Я же говорю, может кому и будет интересно…
                      –7
                      Вы, похоже, один из тех людей, которые готовы работать на голом энтузиазме.
                      Может Вам основать википедию для школьников?
                      Можно выбирать «класс» вместо языка и читать статьи доступным языком.

                      Кроме фактов, которые можно просто запомнить (например, даты из «истории»), если еще вещи, которые нужно понимать.
                      И без указания текущей базы в этом вопросе — никуда.

                        –2
                        Где вы тут ведите сарказм, господа?
                        Хотя если действительно не согласны с необходимостью доступных статей для школьников…
                      +2
                      А что, вы, простите, имеете против паскаля?
                      Вам сложность алгоритмов объяснять или в синтаксическом сахаре капаться?
                        +1
                        «Паскаль — в принципе для школьников самое то»
                        Где вы тут нашли нападки на паскаль?
                          +1
                          А вот насколько это «самое то» для крупнейшего IT-ресурса рунета?

                          Вот тут нашел, Вирт это не самое то для крупнейшего ИТ-ресурса?
                          Может все алгоритмы на MIXе стоит приводить? :)
                            +3
                            Хватит выискивать нападки там где их нет.

                            Статья рассчитана на школьников 9-10 классов.
                            ИМХО, все кто читает хабр отлично знают этот материал.
                              +1
                              >Статья рассчитана на школьников 9-10 классов.
                              ИМХО, все кто читает хабр отлично знают этот материал.


                              На Хабре полно школьников 9-10 классов.
                              // К.О.
                                0
                                Мне вот как раз впервые хабр показали одиннадцатиклассники Fenniks и NotXakep, когда я учился в 10 классе физ-мат лицея.

                                PS: Хороший пост, внес свою долю в подготовке к завтрашней пересдачи Анализа и разработки алгоритмов :)
                        +1
                        Какая разница на каком языке написано, если вам не качество кода и не крутость алгоритма надо рассмотреть, а оценить его быстродействие?
                          –1
                          Во первых: крутость алгоритма — это часто синоним эффективности и быстродействия.
                          Во вторых: с чего вы взяли, что я осуждаю паскаль? Он идеален для школьников. Для профессионалов я бы приводил описание алгоритма на псевдоязыке.
                          В третьих: в начале статьи рассматривается эффективность использования памяти, и по этому показателю паскаль отстает от других языков. Вспомните ступенчатые массивы например.
                            +1
                            Вы вообще понимаете о чём говорите, статью читали? У вас есть уже готовый алгоритм и вам надо оценить его сложность чтобы дальше уже принимать решения о его оптимизации.

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

                            А псевдокод всегда менее понятен, чем старый-добрый, хорошо знакомый язык.
                              +2
                              Не в обиду будет сказано, но не все начинали с Паскаля. Я вот например совсем его не знаю. Но интуитивно догадался, что есть что =)
                                0
                                Отлично понимаю статью. И ни сколько ее не критикую.
                                Зачем эти нападки.

                                Вы можете реализовать алгоритм на любом языке.
                                Но по сути сам алгоритм — это последовательность действий и он независим от языка.

                                Паскаль не идеален. Кто-то начинал программировать на плюсах. Если тут начать приводить примеры на c++, школьники изучающие паскаль вряд ли поймут.
                                  0
                                  А какоого рода, собственно, «псевдоязык» вы имеете в виду? Большая часть псевдоязыков, которые я видел напоминали сильно упрощённый… паскаль(!). Иногда что-то среднее между упрощённым паскалем и сями (без адресной арифметики, упаси господи). Так какая разница — упрощённый паскаль или просто паскаль? :)
                                  А уж пассаж про эффективность использования памяти… Во-первых, при чём здесь язык, речь ведь об алгоритмах, а во-вторых, если говорить о «псевдоязыке», то о какой эффективности использования памяти языком(!) вообще может идти речь в этом случае???
                            +3
                            Так здесь же школьников полно. Пусть учатся.
                              +2
                              В чем проблема? Про новые свистелки и перделки в новом iPride 4GS можно написать на «крупнейшем IT ресурсе», а про основы теории сложности вычислений нет?
                                0
                                выебнуться хочется просто
                              +19
                              Вы бы код оформили нормально.
                                +2
                                Мне кажется нехорошо константу отбрасывать… надо не по порядку оценивать сложность, а асимптотически…
                                (по-крайней мере меня так учили на теории алгоритмов=))
                                  +1
                                  А что считать одной операцией? Инструкцию процессора? Строчку кода? Важное свойство O()-нотации: она нечувствительна к (разумной) интерпретации одного языка программирования другим.
                                    0
                                    Не туда ответил=(, вот ответ: habrahabr.ru/blogs/algorithm/104219/#comment_3249247
                                      0
                                      А вам не кажется, что это слегка произвольный выбор? Почему выбор именно такой, а не какой-то иначе? Если уж решили заботиться о константе до конца, то нужно учитывать cache-эффекты, branch predictors и т. д. Да и, к примеру, сложения и умножения работают разное время.

                                      Но в целом я согласен, бывает, что асимптотика лучше, но на практике алгоритм хуже (яркий примеры — перемножение матриц методом Штрассена, выбор медианы за детерминированное линейное время, Fibonacci heaps).
                                        0
                                        Ну… в реальности работа того или иного алгоритма будет зависеть не только от языка, но и от процессора и его архитектуры, поэтому точно оценить совсем сложно становиться… Нам-то давали теорию алгоритмов с математическим уклоном, а не программистским. Но если приводить все алгоритмы к одной линейке (т.е. одному языку программирования), то константы оставлять стоит.
                                  –2
                                  В зависимости от алгоритма: в алгоритмах умножения, мы одной операцией считали сложение, в сложение — логическую операцию и т.д. В более сложных алгоритмах типа возведения в степень и перемножения полиномов — уже операция умножения была базовой… Просто в некоторых случая константы такие, что при любых разумных n выгоднее использовать О(n^2), где константа 1, чем О(log(n)), где константа 9999999…
                                    0
                                    О показывает характер зависимости некоей условной «сложности» алгоритма в зависимости от «размера» задачи (входных данных). То есть, насколько вырастет потребность в ресурсах, если объем входных данных изменится.
                                    +3
                                    код нечитабелен, таблица в конце абсолютно неиформативна (что я должен узнать из неё?).

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

                                    ps. 1502 привет!
                                      +2
                                      > Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.

                                      Если мы храним запись для каждой пары точек, то даже при грязной реализации, когда для каждой пары точек две ячейки, общее число ячеек не превышает (10^4)^2 = 10^8 = 100 млн ячеек = (по вашему) = 100 Мб памяти. И не стоит городить огород =)

                                      Ну это так, мелочи. Конечно, есть сложные задачи, и именно они интересны и стоят кучу денег, и именно ради них стоит дерзать.
                                        +1
                                        Таблица времени выполнения алгоритма на основе оценки сложности алгоритма — Does not compute!
                                          0
                                          1) оформите код нормально — он нечитабелен
                                          2) расскажите про гармоническое использование памяти + времени (чаще всего используется в задачах с использованием динамического программирования)

                                          О да, я вот уже два года не могу решить придуманную мной задачу: нужно придумать задачу, которая будет иметь очевидное решение сложностью O(N^N).
                                            0
                                            Дано N чисел. Задача выписать все последовательности длины N из этих чисел, повторения допускаются.
                                              0
                                              Видимо, хотелось, чтобы результат был полиномиален по длине входа.

                                              Ну пусть будет такая задача: дана N-1 функция f_i: {1, ..., N}^2 -> R. Нужно найти последовательность a_1, a_2, ..., a_N такую, что f_1(a_1, a_2) + f_2(a_2, a_3) +… + f_{N-1}(a_{N-1}, a_N) -> max
                                            0
                                            спасибо
                                              0
                                              Главное, чтобы ваше определение сложности, опирающееся на интуитивное понимание что такое программа, не противоречило общепринятому в терминах машины Тьюринга.
                                                0
                                                Запишите скринкаст :) За материал спасибо
                                                  0
                                                  я бы к топику добавил еще заметку про NP
                                                    0
                                                    расскажите, какими книжками пользовались при подготовке? Или что посоветуете посмотреть на эту тему еще?
                                                      +1
                                                      «Алгоритмы: построение и анализ», Кормен, Лейзерсон, Ривест, Штейн
                                                      +1
                                                      у меня в институте был предмет в котором надо было оценивать сложность алгоритмов, но преподаватель сам плохо в этом разбирался, поэтому и нам ничего толком объяснить не сумел. А вам удалось :-) Спасибо. К слову, предмет я сдал «автоматов», т.к. с алгоритмами у меня все было в порядке :-)
                                                        0
                                                        А есть ли для matlab какой-то инструментарий для оценки сложности написанных в нем алгоритмов? возможность измерить время работы программы то есть, а вот выразить численно сложность… может кто в курсе?
                                                          0
                                                          Сомневаюсь, что такая задача алгоритмически разрешима. По крайней мере для «обычных» языков программирования.
                                                          +2
                                                          Вы вот написали уже кучу довольно неплохих статей, ну разве нельзя постараться прилично их оформлять??? Вырви глаз же!
                                                            +1
                                                            Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

                                                            Это определение неверно. О-большое — это верхняя оценка на время работы программы. А именно, говорят, что для функций f и g f=O(g) если существует такая константа c и число n0, что для любого n >= n0 верно 0 <= f(n) <= cg(n).
                                                              0
                                                              Гм, по Вашей системе получается, что, например, префикс-функция считается за кварат. Так что Вы пропустили достаточно большую часть теории оценки — амортизационный анализ.
                                                                0
                                                                Смысла нет уходить в О нотацию — без нешкольной математики слишком много голых фактов на веру. У того же Саттера есть объяснения сложности и времени выполнения где-то в начальных главах на вполне интуитивном уровне.
                                                                  0
                                                                  Смысл этой статьи? Если это обычная лекция ВУЗА. У нас в ВУЗЕ эта была 3 лекцией по предмету Алгоритмы и структуры данных.
                                                                    0
                                                                    Погодите, я не понял почему O(N^2 )*O(N^3 )=O(N^5) и O(N^2 )+O(N^3 )=O(N^3)?
                                                                      0
                                                                      Потому что N^2*N^3=N^5.
                                                                      0
                                                                      Вы знаете, отучился в школе с углубленным изучением информатики, потом на инженера программиста в ВУЗе. В итоге только в ВУЗ дали какие то крупицы (как я после института понял на работе) сложности алгоритмов, вот такой бы материальчик в школе, просто и доступно, но уже много чего дает… В общем успехов с этим курсом, полезное дело, не то что для школы, для многих вузов.
                                                                        0
                                                                        Ооо, что то мне кажется… а это случайно не лицей 1502?
                                                                          0
                                                                          Я там и читаю этот курс, а что?
                                                                            0
                                                                            Я там учился и посещал этот курс, кажется это был год, когда вы начинались читать этот курс. Хабр тесен.

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

                                                                        Самое читаемое