Асимптотическая оценка вычислительной сложности алгоритма

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

Используются асимптотические оценки двух видов: O(n) и o(n).

Функцию f(n) определяется как O(j(n)), и говорят, что она порядка j(n) если

Порядок f(n) обозначают как f(n)= O(j(n))

Функция f(n) имеет порядок o(j(n)), если

Например, если f(n)=5n³-3n²+2n+6, то f(n)=О(n³), так как

И f(n)=о(n^3,1), так как

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

Моделью схемы является гиперграф H(X,U), в котором множествам элементов Э и цепей С схемы поставлены во взаимно-однозначные соответствия мн-ва вершин Х и ребер U. Гиперграф задан мн-вами вершин Х={xi / i=1}, ребер U={uj / j=1,m} и многозначными отображениями Х в U – ГХ ={Гxi / i=1,n} и U в Х – ГU = {Гuj / j=1,m}. Идея свободной декомпозиции схемы соединения элементов заключается в следующем: начиная с первого уровня (количество элементов, подлежащих объединению равно n), определяем показатели связности всех пар вершин графа.

, где Ui= Гxi, Uj= Гxj.

Далее процесс повторяется до тех пор, пока не останутся две последние вершины.

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

Алгоритмическая модель процесса свободной декомпозиции без учета операций корректировки гиперграфа имеет следующий вид ( выполняются пп. 1-3):

1. : подсчитываем , где ,

2. Находим , такой что

3. Объединяем в одну вершины х_к и х_r

Количество операций сравнения, необходимых для выполнения п.1. равно . Выбор пары вершин с максимальным показателем связности в п.2. потребует сравнений. Суммируя по получим:

В итоге