Математический анализ алгоритмов

    * Вычитание: [a,b] − [c,d] = [a − d, b − c]

    * Умножение: [a,b] × [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]

    * Деление: [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]

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

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

АСИМПТОТИЧЕСКИЙ АНАЛИЗ ФУНКЦИЙ

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

     Оценка (тетта). Пусть f(n) и g(n) - положительные функции положительного аргумента, n ≥ 1 (количество объектов на входе и количество операций - положительные числа), тогда:

     f(n) = (g(n)),

     если существуют положительные с₁, с₂, n₀, такие, что:

     с₁ * g(n)  f(n)  c₂ * g(n), при n > n₀

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

     Оценка О (О большое). В отличие от оценки o, оценка О требует только, что бы функция f(n) не превышала g(n) начиная с n > n0, с точностью до постоянного множителя:

      c > 0, n0 > 0 :

     0 < f(n),  c * g(n), n , n0

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

     Например, для всех функций:

     f(n)=1/n, f(n)= 12, f(n)=3*n+17, f(n)=n*Ln(n), f(n)=6*n² +24*n+77

     будет справедлива оценка О(n² )

     Указывая оценку О есть смысл указывать наиболее «близкую» мажорирующую функцию, поскольку например для f(n)= n² справедлива оценка О(2ⁿ), однако она не имеет практического смысла.

     Оценка  (Омега). В отличие от оценки О, оценка o является оценкой снизу - т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:

      c > 0, n0 >0 :

     0 < c * g(n) > f(n) 

     Например, запись (n*Ln(n)) обозначает класс функций, которые растут не медленнее, чем g(n) = n*Ln(n), в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

     Асимптотическое обозначение О восходит к учебнику Бахмана по теории простых чисел (Bachman, 1892), обозначения о , О введены Д. Кнутом - (Donald Knuth) [6].

     Отметим, что не всегда для пары функций справедливо одно из асимптотических соотношений, например для f(n)=n^1+sin(n) и g(n)=n не выполняется ни одно из асимптотических соотношений.

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