Пример 2. Алгоритм нахождения факториала числа.

Для i от 1до N с шагом 1
Нц
f=f*i;

Кц;

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

О(N*O(1))=O(N)

В подобной ситуации принято говорить, что алгоритм имеет линейную сложность О(N).

Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.
Для i от 1 до N с шагом 1
Нц

Для j от1 до N с шагом 1
Нц

…

Кц

Сложность этой программы О(N²).

Пример 3 . Алгоритм нахождения максимального элемента в каждой строке для матрицы A[NxN].

Для i от 1 до N с шагом 1

Нц

max=A[i,1];

Для j от 1 до N с шагом 1

Нц

Если (A[i,j]>max) То

С В А max=A[i,j];

Все

Кц

Вывод(max);

Кц

В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N.

Это определяет сложность алгоритма O(N^2).

О(А)=О(1)

О(В)=О(N)*(О(А)+О(1))= О(N)*(О(1)+О(1))= О(N)*(О(1))= О(N*О(1))= О(N)
О(С)= О(N)*(О(1)+О(В))= О(N)*(О(1)+О(N))= О(N)*О(N)= О(N*N)= О(N²)

Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением 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) от изменения размера задачи более очевидной.

Пример 4. Вычислить сумму ряда 1+х¹+х²+х³+х⁴+...+хⁿ

Псевдокод алгоритма.

Алгоритма Сумма_ряда(N,x)

Начало

F s=0;

Для k от 0 до N с шагом 1

Нц

С y=1;

Для i от 1 до k с шаг 1

Е Нц

В А Y=y*x;

Кц

Д s=s+y;

Кц

G Вывод(s);

Конец

Оценим его сложность.

О(А)=1

О(В)=О(N)*О(1)=О(N*О(1))= О(N)
О(С)=О(1)

О(Д)=О(1)

О(E)=О(N)*(О(N)+О(1)+О(1))=О(N)*О(N)= О(N*N)= О(N²)

О(F)=О(1)

О(G)=О(1)

О(1)+ О(N²)+О(1)= О(N²)

При использовании вложенных циклов сложность получена O(n²).

Можно ли улучшить эффективность алгоритма, понизив порядок его сложности?

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

Псевдокод алгоритма.

Алгоритма Сумма_ряда(N,x)

Начало

s=1;

Для k от 1 до N с шагом 1

Нц

В А Y=y*x;

s=s+y;

Кц

Вывод(s);

Конец

О(А)=(О(1)+О(1)=О(1)

О(В)= О(N)*О(А)= О(N)*О(1)=О(N*О(1))= О(N)

О(1)+ О(N)+О(1)= О(N)

Пример 5. Алгоритм "Тройки Пифагора"

Найти такие тройки натуральных чисел не превосходящих заданного n, чтобы x²+y²=z²

Псевдокод алгоритма

Алгоритм ТройкиПифагора(n)

Начало

Для x от 1 до n с шаг 1

Нц

Для y от x до n с шаг 1

Нц

Для z от y до n с шаг 1

E Нц

G I Если (y<=x*2)и (z<=x*2)и (z*z=x*x+y*y)

H То Вывод(x,y,z);

Все

Кц

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

O(H)= O(доминанты условия)+ O(1)=O(1);
O(I)=O(N)*(O(H))= О(N);
O(G)=O(N)*( O(I))=O(N)*( O(N))=O(N²);
O(E)=O(N)*O(G)=O(N)* O(N²)= O(N³);
Сложность данного алгоритма O(N³).