Какие существую оценки сложности

Sander

Интересую оценки снизу сложности алгоритмов. Каковы стандартные приемы проведения таких оценок, какие есть теоремы на этот счет.
Например, если есть функция f(a,b)=c.
И мы знаем, что для любого a есть N значений b, для которых зачения функции f различны,
можно ли утверждать, что сложность вычисления функции f будет больше чем ln_2 (N) ?

Xephon

все-таки M или N?
сложность в каких операциях (базисе)?
ф-ция f(a,b)=b вычисляется довольно просто, и удовлетворяет исходным условиям

Sander

виноват, N

Sander

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

v1160908

Смотря какие рассматривать алгоритмы.
Например, если алгоритм==схема из функциональных элементов &&,||,!, то как правило удается получать линейные нижние оценки. Например, если f(x1,...,xn) существенно зависит от всех переменных, то L(f)>=n-1. Для некоторых функций удается более хитрые линейные оценки получать. Например, если f(x1,...,xn)=x1+...+xn (mod 2 то L(f)=4n-4 (верхняя оценка совпадает с нижней). Доказываются такие оценки как правило какой-нибудь хитрой подстановкой констант вместо некоторых переменных и анализом, что при этом получается.
Известно, что максимальная сложность булевой функции от n переменных асимптотически равна 2^n/n, но примеры таких функций приводить очень трудно. Конечно, есть некоторые извращения. Например, если x1,...,xn - код формулы над натуральной переменной y из операций сложения, вычитания (усеченного умножения, деления (целая часть возведения в степень, констант (например, в лексикографическом порядке y1,...,yn - двоичная запись y, f(x1,...,xn,y1,...,yn) =1, если значение формулы=0, 0 иначе. Известна экспоненциальная нижняя оценка для f.
Иногда рассматривают какую-нибудь арифметическую сложность, например, рассматривают схемы из арифметических элементов и какие-нибудь арифметические задачи типа умножения матриц или полиномов, преобразования фурье и т.д. По-моему, для каких-то таких задач при некоторых предположениях удается доказывать оценки типа n*log n (могу врать).
Для машин Тьюринга или каких-нибудь клеточных схем иногда удается получать квадратичные оценки с помощью метода следов (оценивают количество переданной информации из одной части устройства а другую).
Оставить комментарий
Имя или ник:
Комментарий: