krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
[теории сложности вычислений]оценки сложности алгоритмов снизу
16.04.2009 03:39
|
|
|
заранее прошу не пинать особо за возможно детскую терминологию.
Допустим есть алгоритм X, который вычисляет по объектам O_i(N) результаты R_i(N), при этом количество различных результатов равно K(N).
Есть ли в теории сложности вычислений утверждения о том, что тогда сложность алгоритма X оценивается снизу как ln_2(K(N))?
|
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 04:04
|
|
|
Особого результата тут не нужно. Если выход алгоритма - битовая строка, она будет в худшем случае не короче log K(N), поэтому если она выводится по битам, то это будет тривиальная оценка снизу на число шагов.
|
|
|
krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: Vlad]
16.04.2009 04:10
|
|
|
что значит особого результата не нужно?
То что ты написал я и так понимаю.
я вот например сходу не смогу дать "правильное" формальное определение алгоритма и оценки его сложности.
поэтому суть заданного вопроса в том, чтобы меня отослали к какой-нибудь авторитетной книге. Желательно указав название теоремы, или раздел в котором она сформулирована.
ЗЫ
если придираться к твоему доказательству - то откуда ты взял, что результат - битовая строка и выводится по битам?
а если задать определение, что результаты это сроки из дублирующихся битов - то будет ли отсюда следовать что сложность оценивается как 2ln(K(N))?
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 09:19
|
|
|
Мне кажется, что нижняя оценка будет O(K(N)) 
|
|
|
krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: FMX]
16.04.2009 11:18
|
|
|
нет, есть примеры для логарифма (поиск по бинарному дереву).
а вообще это зависит от вычислительной машины.
например, для тьюринга может быть и O(K(N))
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 12:31
|
|
|
Quote:
например, для тьюринга может быть и O(K(N))
Для Тьюринга здесь длина результата имеет значение.
а она >= const*log(K(N)), если результаты - это строки в алфавите из >=2 символов
и >=K(N), если алфавит из одного символа
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 12:32
|
|
|
|
|
|
krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: reincarnation]
16.04.2009 12:55
|
|
|
N - некоторое число - характеристика группы объектов.
введено в силу того, что сложность алгоритма принято мерять не для заданных входных данных, а для их набора, задаваемого неким параметром,
например это может быть размер входной матрицы, или размер обрабатываемого графа или что-нибудь подобное, в зависимости от исследуемой задачи.
|
|
|
krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: reincarnation]
16.04.2009 12:59
|
|
|
для всех машин существенна длина результата.
например, если определить выч. машину, сказав, что результат выводится в виде 0,1 при этом на вывод
тратится одна вычислительная операция, то будут верны рассуждения поста, написанного Vlad-ом.
просто тьюринг хорошо формализуется и в нем все известно и понятно,
но он довольно далек от практики, поэтому мало интересует.
|
|
|
reincarnation
|
|
knight
|
|
|
|
|
|
|
Рег.: 12.09.2006
|
|
Сообщений: 719
|
|
|
|
Рейтинг: 666
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 13:03
|
|
|
Quote:
но он довольно далек от практики, поэтому мало интересует.
А что интересует?
В общем случае результат - это слово в некотором конечном алфавите
И естественно предполагать, что на "вывод" результата требуется количество операций, пропорциональное его длине.
Тогда аналогичное рассуждение проходит.
|
|
|
krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: reincarnation]
16.04.2009 16:46
|
|
|
да, вроде все правильно
Интересует какое-нибудь формальное определение алгоритма, которое можно применять к существующим компьютерам.
Также интересует то, в какой книжке оно сформулировано и хотелось бы чтобы там было подобное утверждение про сложность.
|
|
|
Non_trivial
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 06.12.2006
|
|
Сообщений: 335
|
|
Из: ГЗ
|
|
Рейтинг: 101
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 18:31
|
|
|
ботай "машину произвольного доступа"
|
|
|
krendel
|
|
|
|
|
|
|
|
|
Рег.: 20.10.2003
|
|
Сообщений: 14379
|
|
|
|
Рейтинг: 10274
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: Non_trivial]
16.04.2009 18:54
|
|
|
о круто, это уже почти то, о чем я мечтал.
жаль они вычитать умножать и делить не умеют 
но направление я понял, спасибо
|
|
|
sonte
|
|
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 1077
|
|
Из: this country
|
|
Рейтинг: 461
|
|
Re: [теории сложности вычислений]оценки сложности алгоритмов снизу
[re: krendel]
16.04.2009 21:08
|
|
|
Вообще говоря, здесь нужно уточнять используемую модель вычислений и меру сложности. Например, для той модели, в которой определяются сублинейные по памяти классы задач (L, скажем) утверждение будет неверно. (Сложностью в этом случае считается количество используемой reusable памяти, а для ввода и вывода используются, скажем, клавиатура и принтер. Программа, которая просто копирует вход на выход, производит массу различных результатов, но использует лишь константную память.) От модели более-менее не зависят утверждения, верные "с точностью до полинома".
Чтобы правильно задать вопрос, полезно сначала почитать что-нибудь по теории сложности алгоритмов (Ахо, Хопкрофт, Ульман, Построение и анализ вычислительных алгоритмов; Sipser, Introduction to the Theory of Computation; Papadimitriou, Computational Complexity - все эти книги есть в колхозе).
|
|
Список
Плоский
Дерево
