space-complexity - 如何计算算法的 kolmogorov 复杂度？

Question

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

Answer 1

这个问题不太对。

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

已经正式证明无法计算字符串的 Kolmogorov 复杂度。在实践中，您可以通过上限进行近似。

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

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

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

忽略你问题的 kolmogorov 复杂性部分，只看@templatetypedef 所做的空间复杂度（即内存占用）方面，你提到的标准太宽松了，你只能说算法的下空间界限是 O (1) 和上界 O(n)，其中 n 是输出。

Answer 2

不，我不相信。考虑需要空间 Θ(1) 的算法“打印 01”，以及需要空间 Θ(n) 的算法“将输入字符串的长度加倍，然后打印 01”。两种算法都符合您提供的标准，因此只要给出这些标准，您就无法说出算法的空间复杂度。

希望这可以帮助！