Supposons que pour diverses chaînes d'entrée, un algorithme génère une chaîne binaire avec le même nombre de 0 et de 1. La sortie pour deux chaînes d'entrée différentes peut être identique ou non. Peut-on dire quelque chose sur la complexité spatiale de l'algorithme?Comment calculer la complexité de kolmogorov d'un algorithme?
Non, je ne crois pas. Considérons l'algorithme "print 01", qui nécessite l'espace Θ (1), et l'algorithme "double la longueur de la chaîne d'entrée, puis print 01", ce qui nécessite de l'espace Θ (n). Les deux algorithmes répondent aux critères que vous avez fournis, donc, compte tenu de ces critères, vous ne pouvez rien dire sur la complexité de l'algorithme.
Espérons que cela aide!
La question n'est pas tout à fait juste.
La complexité de Kolmogorov K (x) ne s'applique pas aux programmes, elle s'applique à une chaîne x. Plus précisément, la complexité de Kolmogorov d'une chaîne x est la longueur minimale du programme nécessaire pour calculer une chaîne particulière x.
Il a été formellement prouvé que l'on ne peut pas calculer la complexité de Kolmogorov d'une chaîne. En pratique, vous pouvez approximer via une limite supérieure.
Le présent document par Ferbus-Zanda et Griorieff vous donne la théorie http://arxiv.org/abs/1010.3201
Une façon intuitive de penser à une telle limite approximative supérieure est de considérer la durée d'un programme de compression qui peut décomprimer à une chaîne particulière.
En appliquant cela à votre problème, la chaîne que vous décrivez est une chaîne binaire aléatoire, doublée. La chaîne d'entrée agit comme une graine pour le générateur de nombres aléatoires. En ignorant la partie complexité de votre question, et en regardant seulement l'aspect de la complexité de l'espace (empreinte mémoire) comme @templatetypedef, les critères que vous mentionnez sont si lâches que tout ce que vous pouvez dire, c'est que l'espace inférieur l'algorithme est O (1) et la borne supérieure O (n), où n est la sortie.