Асимптотическая сложность

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

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

Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).

f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n)<=f(n)<=c2*g(n), при n>n0.

Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n), приведенное неравенство называется асимптотическим равенством, а само обозначение Θ символизирует множество функций, которые растут “так же быстро”, как и функция g(n) – т.е. с точностью до умножения на константу. Как следует из приведенного неравенства, оценка Θ являет собой одновременно и верхнюю и нижнюю оценки сложности. Не всегда есть возможность получить оценку в таком виде, поэтому верхнюю и нижнюю оценки иногда определяют отдельно.
Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).
f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0<=f(n)<=cg(n), при n>n0.
Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).
f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0<=cg(n)<=f(n), при n>n0.
Как следствие: асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего под оценкой сложности понимают верхнюю оценку сложности. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.

{$APPTYPE CONSOLE}

uses
SysUtils;
var n:Integer;
function result(n:integer):Integer; //ôóíêöèÿ ïîäñ÷åòà êîëè÷åñòâà äåëèòåëåé
var i:Integer;
begin
result:=0;
for i:= 2 to n div 2 do
if n mod i =0 then
result:=result+1;
end;

begin
read(n); // ââîä ÷èñëà
write(result(n));
readln;
readln;
end.
end.

4. Рекурсия с запоминанием (прозрачный вариант динамического программирования). Пример быстрого вычисления биномиальных коэффициентов по формуле C(n,m)=C(n-1,m)+C(n-1,m-1)

Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память. Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:

создать глобальный массив FD, состоящий из нулей;

после вычисления числа F(n) поместить его значение в FD[n];

в начале рекурсивной процедуры сделать проверку на то, что FD[n] = 0 и, если, то вернуть FD[n] в качестве результата, а иначе приступить к рекурсивному вычислению F(n).

{Функция на Pascal}

function C(m, n:Byte):Longint;

Begin

If (m=0) or (m=n)

Then C:=1

Else C:=C(m, n-1)+C(m-1, n-1)

End;

{Процедура на Pascal}

Procedure C(m, n: Byte; Var R: Longint);

Var R1, R2: Longint;

Begin

If (m=0) or (m=n)