37、计算机中的熵与算法复杂度解析

计算机中的熵与算法复杂度解析

在计算机科学领域，熵和算法复杂度是两个重要的概念。熵主要涉及随机数生成，而算法复杂度则用于衡量算法的性能和可扩展性。下面将详细介绍这两个方面的内容。

1. 熵与随机数生成

1.1 熵的概念起源

在信息领域，伟大的数学家约翰·冯·诺伊曼建议使用“熵”这个术语，因为当时没人真正理解它的含义。香农采纳了这个建议，如今这个术语有时被称为香农熵。不过，一些科学家认为这个术语的双重用途容易引起混淆，在讨论信息时更倾向于使用“不确定性”一词。而内核黑客们觉得“熵”听起来很酷，鼓励继续使用。

1.2 香农熵在随机数生成中的重要性

在讨论随机数生成器时，香农熵是一个重要的属性。它以每个符号的比特数来衡量，高熵意味着字符序列中有用信息较少，而随机噪声较多。

内核维护着一个熵池，它接收来自非确定性设备事件的数据。理想情况下，这个池中的数据应该是完全随机的。为了跟踪熵池中的熵，内核会对池中的数据不确定性进行测量。当内核向池中添加数据时，会估计添加数据的随机程度；反之，当从池中移除数据时，会降低熵的估计值。这个测量值被称为熵估计。如果熵估计值为零，内核可以选择拒绝随机数请求。

内核随机数生成器在 1.3.30 版本的内核中引入，其代码位于内核源码的drivers/char/random.c文件中。

1.3 随机数生成器的设计与实现

计算机本身是可预测的设备，很难在完全编程的系统中找到随机性。然而，计算机的环境中充满了可获取的非确定性噪声，例如各种硬件设备的定时和用户与计算机的交互。像按键之间的时间间隔、鼠标的移动