问在运行时更改数据结构表示:寻找其他示例

EN

在许多情况下，为了实现更有效的算法，需要对输入表示进行转换。我甚至要说，这是一个重要的方式来思考设计有效的算法在一般情况下。我想到的一些例子是：

• HeapSort.它的工作方式是将原始输入列表转换为二进制堆(可能是最小堆)，然后反复调用remove-min函数以按排序顺序获取list元素。渐近地，它是与最快的基于比较的排序算法相联系的.
• 在列表中查找重复项。如果不更改输入列表，这将花费O(n^2)时间。但是，如果可以对列表进行排序，或者将元素存储在哈希表或Bloom过滤器中，则可以在O(n log n)时间内找到所有重复项。
• 求解线性规划。线性规划(LP)是一类具有广泛应用前景的优化问题。解决LPs最重要的技术之一是二重性，这意味着将你原来的LP转换成所谓的“对偶”，然后再解决这个对偶。根据您的情况，解决双重问题可能比解决原始(“原始”) LP容易得多。这本书的章节以原始/双LPs的一个很好的例子开始。
• 乘非常大的整数或多项式。已知最快的方法是使用快速傅立叶变换，请参阅这里或这里，以获得一些很好的描述。其基本思想是将多项式的通常表示形式(系数列表)转换为求值基础(在某些精心选择的点上对该多项式的求值列表)。计算基础使乘法变得琐碎--您只需将每对评估相乘即可。现在，在求值的基础上有乘积多项式，然后插值(与求值相反)，得到系数，就像你想要的那样。快速傅里叶变换(FFT)是一种非常有效的求值和插值方法，它比直接处理系数的速度要快得多。
• 最长的公共子字符串。如果您想要找到出现在一堆文本文档中最长的子字符串，最快的方法之一是从每个文档创建一个后缀树，然后将它们合并在一起，找到最深的公共节点。
• 线性代数.通过将原始矩阵转换为规范形式(如Hermite范式或计算QR分解 )，可以最有效地执行各种矩阵计算。这些矩阵的交替表示使得求逆、行列式或特征值等标准事物的计算速度快得多。

当然，除了这些例子外，还有很多例子，但我试图想出一些不同的例子。