如何计算算法的柯尔莫哥洛夫复杂度？

Question

假设对于各种输入字符串，算法生成具有相同数量的 0 和 1 的二进制字符串。两个不同输入字符串的输出可能相同也可能不同。我们能谈谈算法的空间复杂度吗？

Answer 1

这个问题不太对。

柯尔莫哥洛夫复杂度 K(x) 不适用于程序，它适用于字符串 x。更具体地说，字符串 x 的柯尔莫哥洛夫复杂度是计算特定字符串 x 所需的最小程序长度。

已经正式证明，人们无法计算字符串的柯尔莫哥洛夫复杂度。在实践中，您可以通过上限进行近似。

Ferbus-Zanda 和 Griorieff 的以下论文为您提供了理论http://arxiv.org/abs/1010.3201

考虑这种近似上限的直观方法是考虑可以解压缩为特定字符串的压缩程序的长度。

将其应用于您的问题，您描述的字符串是一个随机二进制字符串，加倍。输入字符串充当随机数生成器的种子。

忽略问题的柯尔莫哥洛夫复杂度部分，只考虑空间复杂度（即内存占用）方面，就像 @templatetypedef 所做的那样，你提到的标准是如此宽松，以至于你只能说算法的下空间界限是 O (1) 和上限 O(n)，其中 n 是输出。