优化和压缩之间有关系吗？

Question

优化就是用更少的资源做更多的计算。压缩就是用更少的钱说更多的话。这两者之间有关系吗？你能压缩计算吗？

Answer 1

是。问得好。连接是。让我极大地简化它：

在a)数据量和b)信息量之间存在差异。数据是某物的物理量，例如磁盘上或通信线路上的位。信息是它告诉任何正在阅读它的人的信息，作为衡量标准，它总是小于或等于承载它的数据。数据超过其承载的信息的量称为其冗余度。压缩所做的是通过减少冗余来减少数据，使其更接近其信息内容。

那么计算呢？可以将程序想象成一个信息通道，获取输入数据并对其进行处理以识别其信息。当程序结束时，它“知道”关于输入的一定数量的信息。它执行的每个基本操作都是获得(或丢失)信息的操作，直到获得所有信息时才结束。

示例:在包含1024个数字的表中搜索特定的键值。当找到密钥时，已经获取了10位信息，因为需要10位来指示表中数字的位置。如果使用二进制搜索，则需要10次比较，因此每次比较都是“学习”一位。如果键可以直接用作表中的索引，则有一种更快的方法。在这种情况下，索引操作在单个步骤中“学习”所有10位。有一种速度较慢的方法-线性搜索，它平均需要512次比较。在这种方法中，每次比较只得到一小部分比特。(这就是它很慢的原因。)

因此，如果计算机操作类似于数据，优化将尝试最小化给定信息量的操作数量，而压缩尝试最小化给定信息量的数据位数。

Answer 2

这是算法中的一个常见权衡:用额外的空间换取更快的计算速度(查找表中可能的值)，或者相反的(二进制搜索或类似的)。我建议你读一读空间和时间的复杂性。你也许能找到一些小窍门来帮助你优化或压缩，无论你需要更多。