如何计算算法的柯尔莫哥洛夫复杂度？
假设对于各种输入字符串，算法生成具有相同数量的 0 和 1 的二进制字符串。两个不同输入字符串的输出可能相同也可能不同。我们能谈谈算法的空间复杂度吗？
Suppose for various input strings an algorithm generates binary string with same number of 0's and 1's. The output for two different input strings may or may not be the same. Can we say anything about the space complexity of the algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这个问题不太对。
柯尔莫哥洛夫复杂度 K(x) 不适用于程序，它适用于字符串 x。
更具体地说，字符串 x 的柯尔莫哥洛夫复杂度是计算特定字符串 x 所需的最小程序长度。
已经正式证明，人们无法计算字符串的柯尔莫哥洛夫复杂度。在实践中，您可以通过上限进行近似。
Ferbus-Zanda 和 Griorieff 的以下论文为您提供了理论 http://arxiv.org/abs/1010.3201
考虑这种近似上限的直观方法是考虑可以解压缩为特定字符串的压缩程序的长度。
将其应用于您的问题，您描述的字符串是一个随机二进制字符串，加倍。输入字符串充当随机数生成器的种子。
忽略问题的柯尔莫哥洛夫复杂度部分，只考虑空间复杂度（即内存占用）方面，就像 @templatetypedef 所做的那样，您提到的标准非常宽松，您只能说算法的空间下限是 O (1) 和上限 O(n)，其中 n 是输出。
The question isn't quite right.
Kolmogorov complexity K(x) doesn't apply to programs, it applies to a string x.
More specifically, the Kolmogorov complexity of a string x is the minimum program length needed to compute a particular string x.
It has been formally proven that one can't compute the Kolmogorov complexity of a string. In practice, you can approximate via an upper bound.
The following paper by Ferbus-Zanda and Griorieff gives you the theory http://arxiv.org/abs/1010.3201
An intuitive way of thinking about such an approximate upper bound is to consider the length of a compression program that can decompress to a particular string.
Applying this to your problem, the string you describe is a random binary one, doubled. The input string acts a seed for the random number generator.
Ignoring the kolmogorov complexity part of your question, and just looking at space complexity (ie. memory footprint) aspect as @templatetypedef did, the criteria you mention are so loose that all you can say is that the lower space bound for the algorithm is O(1) and the upper bound O(n), where n is the output.
不，我不这么认为。考虑算法“打印 01”，它需要空间 θ(1)，以及算法“将输入字符串的长度加倍，然后打印 01”，它需要空间 θ(n)。两种算法都满足您提供的标准，因此只要给出这些标准，您就无法说出有关算法的空间复杂度的任何信息。
希望这有帮助！
No, I don't believe so. Consider the algorithm "print 01," which requires space Θ(1), and the algorithm "double the length of the input string, then print 01," which requires space Θ(n). Both algorithms meet the criteria you've provided, so just given those criteria you can't say anything about the space complexity of the algorithm.
Hope this helps!