Оценки сложности алгоритмов снизу

Sander

заранее прошу не пинать особо за возможно детскую терминологию.
Допустим есть алгоритм X, который вычисляет по объектам O_i(N) результаты R_i(N при этом количество различных результатов равно K(N).
Есть ли в теории сложности вычислений утверждения о том, что тогда сложность алгоритма X оценивается снизу как ln_2(K(N?

luherstag

Особого результата тут не нужно. Если выход алгоритма - битовая строка, она будет в худшем случае не короче log K(N поэтому если она выводится по битам, то это будет тривиальная оценка снизу на число шагов.

Sander

что значит особого результата не нужно?
То что ты написал я и так понимаю.
я вот например сходу не смогу дать "правильное" формальное определение алгоритма и оценки его сложности.
 поэтому суть заданного вопроса в том, чтобы меня отослали к какой-нибудь авторитетной книге. Желательно указав название теоремы, или раздел в котором она сформулирована.
ЗЫ
если придираться к твоему доказательству - то откуда ты взял, что результат - битовая строка и выводится по битам?
а если задать определение, что результаты это сроки из дублирующихся битов - то будет ли отсюда следовать что сложность оценивается как 2ln(K(N?

Lokomotiv59

Мне кажется, что нижняя оценка будет O(K(N :o

Sander

нет, есть примеры для логарифма (поиск по бинарному дереву).
а вообще это зависит от вычислительной машины.
например, для тьюринга может быть и O(K(N

vsjshnikova

например, для тьюринга может быть и O(K(N
Для Тьюринга здесь длина результата имеет значение.
а она >= const*log(K(N если результаты - это строки в алфавите из >=2 символов
и >=K(N если алфавит из одного символа

vsjshnikova

Кстати, что такое N?

Sander

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

Sander

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

vsjshnikova

но он довольно далек от практики, поэтому мало интересует.
А что интересует?
В общем случае результат - это слово в некотором конечном алфавите
И естественно предполагать, что на "вывод" результата требуется количество операций, пропорциональное его длине.
Тогда аналогичное рассуждение проходит.

Sander

да, вроде всё правильно
Интересует какое-нибудь формальное определение алгоритма, которое можно применять к существующим компьютерам.
Также интересует то, в какой книжке оно сформулировано и хотелось бы чтобы там было подобное утверждение про сложность.

romanenkoroman1

ботай "машину произвольного доступа"

Sander

о круто, это уже почти то, о чем я мечтал.
жаль они вычитать умножать и делить не умеют :)
но направление я понял, спасибо

kravecnata

Вообще говоря, здесь нужно уточнять используемую модель вычислений и меру сложности. Например, для той модели, в которой определяются сублинейные по памяти классы задач (L, скажем) утверждение будет неверно. (Сложностью в этом случае считается количество используемой reusable памяти, а для ввода и вывода используются, скажем, клавиатура и принтер. Программа, которая просто копирует вход на выход, производит массу различных результатов, но использует лишь константную память.) От модели более-менее не зависят утверждения, верные "с точностью до полинома".
Чтобы правильно задать вопрос, полезно сначала почитать что-нибудь по теории сложности алгоритмов (Ахо, Хопкрофт, Ульман, Построение и анализ вычислительных алгоритмов; Sipser, Introduction to the Theory of Computation; Papadimitriou, Computational Complexity - все эти книги есть в колхозе).
Оставить комментарий
Имя или ник:
Комментарий: