Понятия сложности и эффективности алгоритмов и структур данных. Главные принципы, лежащие в основе создания эффективных алгоритмов От чего зависит эффективность алгоритма

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

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

Важен порядок роста времени выполнения алгоритма в зависимости от n

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

Виды анализа: математический и эмпирический

Измерение времени выполнения алгоритма

1. Непосредственное (эмпирический анализ)

2. Определение количества базовых операций, которые должен выполнить алгоритм при обработке входных данных размера n (математический анализ)

Порядок роста

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

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

Существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от конкретных особенностей входных данных (пример – поиск).

Эффективность измеряют для:

  • наихудшего случая
  • наилучшего случая
  • среднего случая

    • Пример: среднее количество операций сравнения при поиске:

    Итак:

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

    Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

    Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

    HTML-версии работы пока нет.
    Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.

    Подобные документы

      Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.

      курсовая работа , добавлен 07.07.2013

      Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.

      дипломная работа , добавлен 12.08.2017

      Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе.

      реферат , добавлен 27.11.2012

      Проблема улучшения качества отпечатков пальца с целью повышения эффективности работы алгоритмов биометрической аутентификации. Обзор алгоритмов обработки изображений отпечатков пальцев. Анализ алгоритма, основанного на использовании преобразования Габора.

      дипломная работа , добавлен 16.07.2014

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

      курсовая работа , добавлен 21.06.2013

      Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.

      контрольная работа , добавлен 16.12.2012

      Переход от словесной неформальной постановки к математической формулировке данной задачи. Оценка различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки. Реализация алгоритмов на одном из языков программирования.

      курсовая работа , добавлен 25.06.2013

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

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

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

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

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

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

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

    Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы , оптимизирующий компилятор , оптимизация циклов , оптимизатор объектного кода , и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».

    Энциклопедичный YouTube

      1 / 5

      ✪ CS50. Асимптотические обозначения

      ✪ 1. Алгоритмы и структуры данных. Введение | Технострим

      ✪ Алгоритмическая эффективность

      ✪ Алгоритм Кнута-Морриса-Пратта

      ✪ 2. Алгоритмы и структуры данных. Списки, стек, очередь, дек | Технострим

      Субтитры

      Вы, вероятно, слышали как люди говорят о быстрых или эффективных алгоритмах для выполнения той или иной задачи, но что именно понимают под быстротой и эффективностью в случае алгоритмов? В действительности говорят не об измерениях реального времени в секундах или минутах. Потому что компьютерное оборудование и программное обеспечение весьма разнообразно. Моя программа может работать медленнее вашей из-за того, что я запустил её на более старом компьютере, или из-за того, что я одновременно играю в сетевую игру какую-нибудь, которая съедает у меня всю память. Или же я запустил свою программу через другое программное обеспечение, которое по-своему взаимодействует с оборудованием на низком уровне. Это всё равно что сравнивать тёплое с мягким. Только то, что у моего более медленного компьютера уходит больше времени на поиск ответа, ещё не значит, что ваш алгоритм более эффективный. Раз мы не можем напрямую сравнивать время исполнения программ в секундах или минутах, то как нам сравнить два разных алгоритма без зависимости от оборудования или программного обеспечения? Чтобы унифицировать способ измерения алгоритмической эффективности, математики и специалисты в области информатики нашли решение в измерении асимптотической сложности программы и так называемой записи "О большое" для её описания. Формальное определение звучит так: Функция f(x) имеет порядок g(x), если существует такое значение "x", "x₀" и некоторая константа "C", для которых f(x) меньше или равно этой константе, умноженной на g(x) для любого "x" большего, чем "x₀". Однако, не пугайтесь формального определения. Что же это значит на самом деле в менее теоретических терминах? Ну, попросту говоря, это способ анализа того, насколько быстро растёт асемптотическое время исполнения программы. То есть по мере увеличения размера входных данных в сторону бесконечности. Скажем, мы сортируем массив из 1000 элементов и массив из 10. Как вырастет время исполнения программы? Например, представьте подсчёт числа символов в строке простейшим способом, проходом всей строки буква за буквой и добавлением единицы к счётчику каждый раз. Говорят, что алгоритм выполняется за линейное время от количества символов (n) в строке. Или кратко, выполняется за O(n). Почему так? Ну, при таком подходе время, требующееся для прохода всей строки, пропорционально числу символов в ней. Подсчёт числа символов в 20-символьной строке займёт вдвое больше, чем подсчёт в 10-символьной строке, потому что придётся посмотреть на все символы, а просмотр каждого символа занимает одинаковое время. По мере увеличения числа символов время исполнения будет увеличиваться вместе с длиной исходных данных. Теперь, допустим, вы решаете, что линейное время, O(n), -- это не достаточно быстро. Возможно, вы храните огромные строки и не можете позволить себе дополнительное время на проход по всем символам, подсчитывая их один за другим. И вы решаете попробовать кое-что другое. Что если число символов для строки уже будет храниться в переменной, скажем, "len". Оно сохраняется в программе раньше, ещё до того, как вы сохранили самый первый символ своей строки. Тогда всё, что вам нужно будет сделать для нахождения длины строки -- это прочитать значение этой переменной. Вам не пришлось бы вообще смотреть на саму строку, а чтение значения переменной "len" предпологается операцией, выполняющейся за асимптотически постоянное время, или O(1). Почему так? Вспомним, что значит асимптотическая сложность. Как время исполнения изменяется по мере роста размера входных данных? Допустим, вы получаете количество символов в более длинной строке. В общем-то, совершенно не важно, насколько она длинная. Хоть миллион символов. Всё, что нужно будет сделать при таком подходе, чтобы найти длину строки -- это прочитать значение переменной "len", которую вы уже получили. Размер входных данных, в нашем случае строки, длину которой мы хотим найти, вообще не будет влиять на то, как быстро выполняется программа. Эта часть вашей программы будет одинаково быстро выполняться на строке из одного символа и на строке из тысячи символов. И вот поэтому программа будет считаться исполняющейся за постоянное время относительно размера входных данных. Конечно же, есть и недостатки. Вы тратите дополнительную память вашего компьютера для хранения переменной, а также дополнительное время, чтобы заполнить её значение. Но смысл в этом всё равно есть. Время получения количества символов в строке вообще не зависит от длины строки. Итак, оно исполняется за O(1) или за постоянное время. Само собой это не обязательно значит, что ваш код выполняет только один шаг. Однако, не важно сколько будет шагов, если их число не меняется при изменении размера входных данных. Оно будет асимптотически постоянным, что мы обозначаем как O(1). Как вы, возможно, предположили есть много различных "больших О" для измерения времени исполнения алгоритмов. Алгоритмы O(n²) асимптотически медленнее алгоритмов O(n). Это значит, что по мере увеличения количества элементов, n, алгоритмы O(n²), в конечном итоге потребуют больше времени, чем алгоритмы O(n). Это не значит, что алгоритмы O(n) всегда выполняются быстрее, чем алгоритмы O(n²), даже в одинаковом окружении на одинаковом оборудовании. Может быть так, что для небольших входных данных алгоритм O(n²) будет и в самом деле работать быстрее, однако, со временем, по мере увеличения размеров входных данных в сторону бесконечности, время исполнения алгоритма O(n²) будет в конце концов затмевать время исполнения алгоритма O(n). Также как и любая квадратичная математическая функция будет в конечном счёте обгонять любую линейную функцию. И не важно насколько велика фора у значения линейной функции в самом начале. Если вы работаете с большими объёмами данных, то алгоритмы, выполняющиеся за O(n²), в итоге замедляют вашу программу, но на небольших размерах входных данных вы этого даже не заметите, скорее всего. Ещё один вид асимптотической сложности -- это логарифмическое время, O(log n). Примером алгоритма, который выполняется так быстро, служит классический алгоритм двоичного поиска для нахождения элемента в предварительно отсортированном наборе. Если вы не знаете, как выполняется двоичный поиск, я сейчас быстренько всё объясню. Скажем, вы ищете число 3 в массиве целых чисел. Берём центральный элемент массива и спрашиваем: "Нужный мне элемент больше, меньше или равен этому?" Если равен -- отлично. Мы нашли нужный элемент, на этом всё. Если больше, то понятно, что наш элемент должен быть в массиве где-то справа, и дальше можно смотреть только в правую часть. Если меньше, тогда понятно, что элемент где-то слева. Затем повторяем этот процесс со всё более короткими массивами, пока не найдём нужный элемент. Этот мощный алгоритм уменьшает размер массива в два раза после каждой операции. То есть для нахождения элемента в отсортированном массиве длины 8 нужно не более (log₂8) или трёх таких операций проверки центрального элемента и выбора нужной половины. В то же время для массива длины 16 понадобится (log₂16) или четыре операции. А это всего одна дополнительная операция при удвоении длины массива. Удвоение размера увеличивает время исполнения всего на один кусок кода. Ещё раз -- проверяем центральный элемент и делим массив. Итак, это называют логарифмическое время, O(log n). Но погоди-ка, скажете вы, а не зависит ли он от того, где в массиве находится искомый элемент? Что если первый же элемент, который мы проверим окажется тем самым? Тогда это займёт всего одну операцию, и не важно насколько большой массив. Именно поэтому в информатике существуют ещё другие понятия для асимптотической сложности, которые отражают производительность в лучшем и худшем случае. Или более строго -- верхнюю и нижнюю границы времени исполнения алгоритма. В наилучшем случае для двоичного поиска наш элемент находится прямо тут -- в центре. Мы находим его за постоянное время вне зависимости от величины остального массива. Для этого используют символ Ω. То есть говорят, что алгоритм выполняется за Ω(1). В лучшем случае он находит элемент очень быстро. Не важно насколько большой массив. Но вот в худшем случае понадобится выполнить (log n) проверок и разделений массива, чтобы найти нужный элемент. Верхняя граница для худшего случая обозначается "большим О", как вы уже знаете. Таким образом получается O(log n), но Ω(1). Для сравнения линейный поиск, в котором мы просматриваем каждый элемент в массиве, чтобы найти нужный, в лучшем случае Ω(1). То есть снова первый элемент оказывается тем самым, что мы ищем. Поэтому не важно насколько большой у нас массив. В худшем случае искомый элемент находится в самом конце. И придётся пройти через все n элементов массива, чтобы его найти. Вот так, если мы ищем 3. То есть его время исполнения O(n), так как оно пропорционально числу элементов массива. Ещё используется символ Θ. С его помощью описываются алгоритмы, у которых лучшее и худшее время одинаковое. Как в случае алгоритма поиска длины строки, о котором мы говорили ранее. Того, где мы сохраняем длину в переменной заранее, а в последствии просто читаем её за постоянное время. Без разницы, какое именно число мы сохраняем в этой переменной, мы будем на него смотреть. В лучшем случае мы смотрим значение и получаем длину строки. То есть Ω(1) или постоянное время для лучшего случая. В худшем случае мы смотрим значение и получаем длину строки. То есть O(1) или постоянное время для худшего случая. Таким образом лучший и худший случаи одинаковые. И можно сказать, что алгоритм исполняется за время Θ(1). Подводя итог, у нас есть хорошие способы рассуждения об эффективности кода без выяснения того, сколько реального времени он потребует для выполнения. Такое время зависит от большого числа внешних факторов, таких как аппаратное и программное обеспечение, а также специфика самого кода. А ещё мы можем чётко рассуждать о том, что будет, когда размер входных данных возрастёт. Если у нас есть алгоритм O(n²), или ещё хуже алгоритм O(2ⁿ), то есть один из самых быстро возрастающих видов, тогда замедление действительно будет трудно не заметить при работе с увеличивающимися объёмами данных. Это и есть асимптотическая сложность. Спасибо за внимание.

    История вопроса

    Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа :

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

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

    Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:

    «В установившихся технических дисциплинах улучшение на 12% легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании»

    Обзор

    Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.

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

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

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

    Теоретический анализ

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

    Некоторые примеры нотации «O» большое:

    Обозначение Название Примеры
    O (1) {\displaystyle O(1)\,} постоянное Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хэш-функции для выбора элемента.
    O (log ⁡ n) {\displaystyle O(\log n)\,} логарифмическое Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева , как и операции в биномиальной куче .
    O (n) {\displaystyle O(n)\,} линейное Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n -битных чисел с использованием сквозного переноса .
    O (n log ⁡ n) {\displaystyle O(n\log n)\,} квазилинейное , логарифмически линйное Вычисление быстрого проеобразования Фурье , пирамидальная сортировка , быстрая сортировка (лучший и средний случай), сортировка слиянием
    O (n 2) {\displaystyle O(n^{2})\,} квадратное Умножение двух n -значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла , быстрая сортировка (худший случай), сортировка выбором , сортировка вставками
    O (c n) , c > 1 {\displaystyle O(c^{n}),\;c>1} экспоненциальное Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования . Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора

    Проверочные испытания: измерение производительности

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

    Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как например Roy Longbottom’s PC Benchmark Collection , а The Computer Language Benchmarks Game сравнивает производительность реализаций типичных задач в некоторых языках программирования.

    Вопросы реализации

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

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

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

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

    Измерение использования ресурсов

    Измерения обычно выражаются как функция от размера входа n .

    Два наиболее важных измерения:

    • Время : как долго алгоритм занимает процессор.
    • Память : как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.

    Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:

    • Прямое потребление энергии : энергия, необходимая для работы компьютера.
    • Косвенное потребление энергии : энергия, необходимая для охлаждения, освещения, и т.п.

    В некоторых случаях нужны другие, менее распространённые измерения:

    • Размер передачи : пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие . Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
    • Внешняя память : память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
    • Время отклика : параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
    • Общая стоимость владения : параметр важен, когда предназначен для выполнения одного алгоритма.

    Время

    Теория

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

    Память

    Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма , чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое .

    Существует четыре аспекта использования памяти:

    • Количество памяти, необходимой для хранения кода алгоритма.
    • Количество памяти, необходимое для входных данных.
    • Количество памяти, необходимое для любых выходных данных (некоторые алгоритмы, такие как сортировки, часто переставляют входные данные и не требуют дополнительной памяти для выходных данных).
    • Количество памяти, необходимое для вычислительного процесса во время вычислений (сюда входят именованные переменные и любое стековое пространство, необходимое для вызова подпрограмм, которое может быть существенным при использовании рекурсии).

    Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.

    Современные компьютеры могут иметь относительно большое количество памяти (возможно, гигабайты), так что сжатие используемой алгоритмом памяти в некоторое заданное количество памяти требуется меньше, чем ранее. Однако, существование трёх различных категорий памяти существенно:

    • Кэш (часто, статическая RAM) – работает на скоростях, сравнимых с ЦПУ
    • Основная физическая память (часто, динамическая RAM) – работает чуть медленнее ЦПУ
    • Виртуальная память (зачастую, на диске) – даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.

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

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

    Дата создания: 2009-03-25 12:50:48
    Последний раз редактировалось: 2012-02-08 06:29:55

    Данная статья - вступительная в разделе "Алгоритмы".

    В данном разделе мы сосредоточимся на двух направлениях: структуры данных и непосредственно алгоритмы.

    С кое-какими структурами данных Вы уже познакомились: массивы, структуры, классы. Это примеры статических структур данных. Т.е. задали мы вначале программы десять элементов массива, в конце программы этих элементов так и осталось десять. На страницах рассылки и в данном разделе мы познакомимся динамическими структурами данных. Некоторые из этих структур просто делают программистскую жизнь легче, без других невозможно построить определённый алгоритм.

    Также структур данных касаются ещё две области программирования, которые мы будем рассматривать: STL и D3DX. В STL (стандартная библиотека шаблонов в C++) собраны математические структуры данных и алгоритмы, а в D3DX (вспомогательная библиотека DirectX) присутствует ряд интересных нам структур, которые непосредственно используются в графических приложениях.

    Эффективность алгоритмов

    В данном - вступительном выпуске мы не будем рассматривать какую-либо конкретную структуру. Здесь мы поговорим об эффективности алгоритмов. Для этого нам потребуется ввести несколько понятий.

    Сразу хочу подчеркнуть, что в данной статье я сознательно упрощаю материал. И с математической точки зрения, некоторые определения в данной статье не корректны. За более точным и полным описанием математических понятий, вам потребуется обратиться к учебникам по алгоритмам.

    Приступим. Есть несколько критериев оценки эффективности алгоритмов. Для простоты мы будем обсуждать только временную эффективность.

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

    Рассмотрим пример: у нас есть массив из десяти элементов. И у нас есть два алгоритма: поиск элемента в массиве и сортировка массива.

    Первый алгоритм ищет в массиве определённое значение. Например, нужно проверить есть ли в массиве число 14. Для этого каждый элемент массива сравнивается с этим числом.

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

    Что у нас здесь есть? Прежде всего размер входных данных. Обозначим его - n . Из нашего примера n = 10 .

    Так вот, эффективность алгоритма - это функция зависящая от размера входных данных. Чем больше входных данных, тем дольше будет выполняться алгоритм.

    Функция в математическом контексте и в программистском понимается примерно одинаково. Есть различия, но пока они для нас несущественны.

    При выполнении алгоритма для каждого входного значения выполняется какая-то базовая операция. В алгоритме поиска - это простое сравнение. При сортировке базовая операция посложнее. Базовая операция тоже влияет на эффективность алгоритма.

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

    Порядок роста

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

    Пример: у нас есть упорядоченный массив из 10 элементов. Представим, что нам нужно найти два числа. Во время поиска оказалось, что первое число находилось в середине массива, а второе - в конце. Теперь возьмём массив из 20 элементов (в два раза больше). И опять, элементы расположены так, что первый элемент оказался в середине, а второй в конце. Эти два случая имеют одинаковый порядок роста: при увеличении размера входных данных в два раза, количество базовых операций необходимых для выполнения алгоритма увеличилось в два раза.

    Примечание: заметьте, что хотя мы и используем один алгоритм в примере, но рассматриваем два случая выполнения этого алгоритма. В данном контексте мы можем говорить о двух разных алгоритмах. Это важно!

    Теперь переходим к самому важному в статье.

    Сравнение порядков роста

    Количество базовых операций за которое выполняется алгоритм - это время выполнения алгоритма. Обозначим его как t(n) .

    И обозначим какую-нибудь простая функция g(n) с которой мы будем сравнивать время выполнения t(n) .

    Для сравнения порядков роста двух алгоритмов используют предел отношения времени выполнения двух алгоритмов.

    При постоянно увеличивающемся n мы вычисляем отношение t(n) к g(n) .

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

    Во втором случае порядок роста t(n) и g(n) одинаковый. с - какая-то константа. Т.е. при увеличении размера входных данных, насколько вырос порядок роста t(n) настолько же вырос и порядок роста g(n) .

    В третьем случае t(n) имеет больший порядок роста. Соответственно результат стремится к бесконечности.

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