Как оценивается эффективность алгоритма. Исследование эффективности разработанных алгоритмов

Главные принципы создания эффективных алгоритмов

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

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

  • 1. Можно ли решить часть задачи? Можно ли, игнорируя некоторые условия, решить оставшуюся часть задачи?
  • 2. Можно ли решить задачу для частных случаев? Можно ли разработать алгоритм, который дает решение, удовлетворяющее всем условиям задачи, но входные данные которого ограничены некоторым подмножеством всех входных данных?
  • 3. Есть ли что-то, относящееся к задаче, что недостаточно хорошо уяснено? Если попытаться глубже вникнуть в некоторые особенности задачи, удастся ли узнать нечто, что поможет подойти к решению?
  • 4. Известно ли решение похожей задачи? Можно ли видоизменить ее решение для решения рассматриваемой задачи? Возможно ли, что эта задача эквивалентна известной нерешенной задаче?

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

Вообще методы подъема относятся к «грубым». Они запоминают некоторую цель и стараются сделать все что могут и где могут, чтобы подойти ближе к цели. Это делает их несколько «недальновидными». Недальновидность метода подъема хорошо иллюстрируется следующим примером. Пусть требуется найти максимум функции у =/(х), представленной графиком (рис. 2.15). Если начальное значение аргумента х = а, то метод подъема даст устремление к ближайшей цели, т.е. к значению функции в точке х = Ь, тогда как подлинный максимум этой функции находится вх = с. В данном случае

Рис. 2.15. Иллюстрация метода подъема метод подъема находит локальный максимум, но не глобальный. В этом и состоит «грубость» метода подъема.

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

Рассмотрим все три метода в задаче о джипе. Пусть требуется пересечь на джипе 1000-километровую пустыню, израсходовав при этом минимум горючего. Объем топливного бака джипа 500 л, горючее расходуются равномерно, по 1 л на 1 км. При этом в точке старта имеется неограниченный резервуар с топливом. Поскольку в пустыне нет складов с горючим, необходимо установить свои собственные хранилища и наполнять их топливом из бака машины. Итак, идея задачи ясна: нужно из точки старта отъезжать с полным баком на некоторое расстояние, устраивать там первый склад, оставлять там какое-то количество горючего из бака, но такое, чтобы хватило вернуться назад. В точке старта вновь производится полная заправка и делается попытка второй склад продвинуть в пустыню дальше. Но где обустраивать эти склады и сколько горючего оставлять в каждом из них?

Подойдем к решению этой задачи с помощью метода отрабатывания назад. С какого расстояния от конца можно пересечь пустыню, имея запас горючего в точности к баков? Рассмотрим этот вопрос для к = 1,2, 3,... пока не найдем такое целое п, что п полных баков позволяет пересечь всю 1000-километровую пустыню. Для к = 1 ответ равен 500 км = 500 л (точка В), как показано на рис. 2.16.

Рис. 2.16.

Можно заправить машину в точке В и пересечь оставшиеся 500 км пустыни. Была поставлена частная цель, потому что нельзя решить сразу исходную задачу.

Предположим, что к = 2, т.е. есть два полных бака (1000 л). Эта ситуация иллюстрируется на рис. 2.16. Каково максимальное значение jCj, такое, что, отправляясь с 1000 л горючего из точки (500 - Xj), можно перевезти достаточно горючего в точку, чтобы завершить поездку, как в случае к = 1. Один из способов определения приемлемого значения х { состоит в следующем. Заправляемся в точке (500 - Xj), едем х { километров до точки В и переливаем в хранилище все горючее, кроме той части, которая потребуется для возвращения в точку (500 - Xj). В этой точке бак становится пустым. Теперь наполняем второй бак, проезжаем Xj километров до В , забираем в В горючее, оставленное там, и из В едем в С с полным баком. Общее пройденное расстояние состоит из трех отрезков по х { километров и одного отрезка ВС длиной 500 км. Поэтому находим из уравнения 3x t + 500 = = 1000 его решение Xj = 500/3. Таким образом, два бака (1000 л) позволяют проехать Z> 2 = 500 +х { = 500(1 + 1/3) км.

Рассмотрим к = 3. Из какой точки можно выехать с 1500 л топлива так, что джип сможет доставить 1000 л в точку (500 - х })? Найдем наибольшее значение х 2 , такое, что, выезжая с 1500 л топлива из точки (500 - Xj - х 2), можно доставить 1000 л в точку (500 - Xj). Выезжаем из точки (500 - Xj - х 2), доезжаем до (500 - х,), переливаем все горючее, кроме х 2 литров, и возвращаемся в точку (500 - Xj - х 2) с пустым баком. Повторив эту процедуру, затратим 4х 2 литров на проезд и оставим (1000 - 4х 2) литров в точке (500 - x L). Теперь в точке (500 - Xj - х 2) осталось ровно 500 л. Заправляемся последними 500 л и едем в точку (500 - Xj), израсходовав на это х 2 литров.

Находясь в точке (500 - Xj), на проезд затрачиваем 5х 2 литров топлива. Здесь оставлено в общей сложности (1500 - 5х 2) литров. Это количество должно быть равно 1000 л, т.е. х 2 = 500/5. Из этого заключаем, что 1500 л позволяют проехать

Продолжая индуктивно процесс отрабатывания назад, получаем, что п баков горючего позволяют нам проехать D n километров, где D n = 500(1 +1/3 + 1/5 + ... + 1/(2п - 1)).

Нужно найти наименьшее значение п, при котором D n > 1000. Простые вычисления показывают, что для п = 7 имеем D ? = 997,5 км, т.е. семь баков, или 3500 л, топлива дадут возможность проехать

  • 977.5 км. Полный восьмой бак - это было бы уже больше необходимого, чтобы перевезти 3500 л из точки А в точку, отстоящую на
  • 22.5 км (1000 - 977,5) от А Читателю предоставляется возможность самостоятельно убедиться в том, что для доставки 3500 л топлива к отметке 22,5 км достаточно 337,5 л. Таким образом, для того чтобы пересечь на машине пустыню из И в С, нужно 3837,5 л горючего.

Теперь алгоритм транспортировки топлива может быть представлен следующим образом. Стартуем из А, имея 3837,5 л. Здесь как раз достаточно топлива, чтобы постепенно перевезти 3500 л к отметке

22.5 км, где джип в конце концов окажется с пустым баком и запасом топлива на 7 полных заправок. Этого топлива достаточно, чтобы перевезти 3000 л к точке, отстоящей на 22,5 + 500/13 км от А, где бак машины будет опять пуст. Последующие перевозки приведут джип к точке, отстоящей на 22,5 + 500/13 + 500/11 км от А, с пустым баком машины и 2500 л на складе.

Продолжая таким образом, мы продвигаемся вперед благодаря анализу, проведенному методом отрабатывания назад. Вскоре джип окажется у отметки 500(1 - 1/3) км с 1000 л топлива. Затем перевезем 500 л топлива в точку В, зальем их в бак машины и доедем без остановки до точки С (рис. 2.17).


Рис. 2.17.

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

Возникает вопрос, можно ли проехать 1000 км, затратив меньше чем 3837,5 л топлива. Оказывается, нельзя. Доказательство этого утверждения довольно сложное. Однако можно высказать следующий, довольно правдоподобный довод. Очевидно, мы действуем наилучшим образом для к = 1. При к = 2 используется план для к = 1 и затем вводится в действие второй бак топлива для того, чтобы оказаться как можно дальше от точки В. Исходная предпосылка для к баков состоит в том, что мы знаем, как действовать наилучшим образом в случае с (к - 1) баками, и отодвигаемся как можно дальше назад с помощью к-то бака.

Итак, в рассмотренной задаче метод отрабатывания назад состоит в том, что задачу решают как бы с конца; метод частных целей состоит в том, что решают не всю задачу сразу, а как бы по частям; и, наконец, метод подъема проявляется в том, что решение отыскивается не сразу, а последовательно, как бы приближаются к нему.

КОНТРОЛЬНЫЕ ВОПРОСЫ

  • 1. Дайте определение объекта, класса, системы, модели.
  • 2. Назовите основные типы моделей.
  • 3. Что такое имитационное моделирование?
  • 4. Какие классификации моделей существуют?
  • 5. Укажите основные этапы моделирования.
  • 6. Что такое алгоритм?
  • 7. Перечислите свойства алгоритма.
  • 8. Какие этапы выполняются при полном построении алгоритма?
  • 9. Что такое блок-схема алгоритма?
  • 10. Дайте определение функционального блока.
  • 11. Какой алгоритм называется структурным?
  • 12. Назовите главные принципы, лежащие в основе создания эффективных алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Итак:

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

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

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

    Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
    Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
    Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 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! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
    В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

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

    Ту часть теории алгоритмов, которая занимается оценкой характеристик алгоритмов, называют метрической. Ее можно разделить на дескриптивную (качественную) и метрическую (количественную) . Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими «вычислений», т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе алгоритм А будет сложнее В , а при другом способе - наоборот.

    Чаще всего алгоритмы оцениваются по требуемой памяти, числу выполняемых операций, времени решения или погрешности вычислений. Эти характеристики зачастую зависят от параметров (размерности) задачи и имеют нелинейный характер. Поэтому в теории алгоритмов существует направление оценки эффективности алгоритмов по асимптотическим оценкам функций: требуемой памяти, времени вычисления и т.п. При этом определяется наиболее существенный параметр функции и исследуется поведение функции при возрастании значений параметра. В ходе исследования пытаются определить, какой характер носит зависимость значений рассматриваемой характеристики алгоритма от параметра. Она может быть линейной (т.е. пропорциональной параметру n), логарифмической (т.е. пропорциональной log n), квадратичной (т.е. пропорциональной n 2) и т.д. Сравнивая асимптотические оценки алгоритмов, решающих одну и ту же задачу, можно выбрать более эффективный алгоритм. Говорят, что значение некоторого параметра T(n) имеет порядок n x , если существуют такие положительные константы k и n o , что для всех n³n o , выполняется неравенство T(n) ≤ k n x .

    Предположим, что n – количество числовых данных, поступающих на вход нескольких разных алгоритмов (А 1 , А 2 , А 3 , А 4 , А 5), которые производят вычисления с одинаковой скоростью - 1000 операций в секунду, но имеют разные асимптотические оценки. В табл.1.8 показаны значения n, которые могут обработать эти алгоритмы в 1 секунду, 1 минуту и 1 час (значения округлены в меньшую сторону до целого числа). Данные табл.1.3 наглядно показывают, что производительность алгоритма (т.е. число данных, обрабатываемых в единицу времени) существенно зависит от характера функции асимптотической оценки.

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