Как вычислить колмогоровскую сложность алгоритма?

Question

Предположим, что для различных входных строк алгоритм генерирует двоичную строку с одинаковыми номерами 0 и 1. Выходные данные для двух разных входных строк могут совпадать или не совпадать. Можем ли мы что-нибудь сказать о пространственной сложности алгоритма?

Answer 1

Вопрос не совсем правильный.

Колмогоровская сложность K (x) не относится к программам, она применяется к строке x. Более конкретно, колмогоровская сложность строки x - это минимальная длина программы, необходимая для вычисления конкретной строки x.

Формально доказано, что невозможно вычислить колмогоровскую сложность струны. На практике вы можете приблизиться через верхнюю границу.

Следующая статья Фербуса-Занды и Гририева дает вам теорию http://arxiv.org/abs/1010.3201

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

Применяя это к вашей проблеме, вы описываете случайную двоичную строку, удвоенную. Входная строка служит начальным числом для генератора случайных чисел.

Игнорируя часть вашего вопроса о колмогоровской сложности и просто глядя на аспект сложности пространства (т.е. объем памяти), как это сделал @templatetypedef, упомянутые вами критерии настолько свободны, что все, что вы можете сказать, это то, что нижнее пространство ограничено Алгоритм O (1) и верхняя граница O (n), где n это выход.

Answer 2

Нет, я не верю в это. Рассмотрим алгоритм «print 01», который требует пробела & theta; (1), и алгоритм «удваивают длину входной строки, затем выведите 01», который требует пробела & theta; (n) Оба алгоритма соответствуют указанным вами критериям, поэтому, учитывая эти критерии, вы ничего не можете сказать о пространственной сложности алгоритма.

Надеюсь, это поможет!