更改

=== '''统计复杂度''' ===

=== '''统计复杂度''' ===

粗略地说，柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑对象中的所有比特，包括随机状态。其主要后果是[math]\displaystyle{ K(x) }[/math]中数值[math]\displaystyle{ x }[/math]被随机性的生成所主导，因此掩盖了对象以及其生成过程中的重要结构。相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟中随机比特时所花费的计算努力。统计复杂度的一个定义性特征是，对于完全随机对象[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列，同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。如果[math]\displaystyle{ s^L }[/math]表示[math]\displaystyle{ x }[/math]的前[math]\displaystyle{ L }[/math]个符号，那么复杂性之间的关系简单地为：

粗略地说，柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑对象中的所有比特，包括随机状态。其主要后果是[math]\displaystyle{ K(x) }[/math]中数值[math]\displaystyle{ x }[/math]被随机性的生成所主导，因此掩盖了对象以及其生成过程中的重要结构。相比之下，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟中随机比特时所花费的计算努力。统计复杂度的一个特征是，对于完全随机对象[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列，同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。如果[math]\displaystyle{ s^L }[/math]表示[math]\displaystyle{ x }[/math]的前[math]\displaystyle{ L }[/math]个符号，那么复杂性之间的关系简单地为：

[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]

[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]

如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总信息量。[math]\displaystyle{ h_μ L }[/math]为允许损失的随机信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。

如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总信息量。[math]\displaystyle{ h_μ L }[/math]为允许损失的信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。

在下图中，展示了柯式复杂度和统计复杂度在从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数，是对信息源不可预测程度的度量，它可以通过香农熵率来衡量其随机性程度。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。

在下图中，展示了柯式复杂度和统计复杂度在从简单周期性到完全随机的过程中的差异。如图(a)所示，柯式复杂度是过程中随机性的单调递增函数，是对信息源不可预测程度的度量，它可以通过香农熵率来衡量其随机性程度。相反，统计复杂度在两个极端点上均为零，并在中间达到最大值（见图(b)）。它基于这样的观点：随机性在统计上是简单的，一个完全随机过程具有零统计复杂度。周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。