我一直在学习后缀数组的创建，我知道我们首先根据第一个字符对所有后缀进行排序，然后根据前 2 个字符，然后是前 4 个字符，依此类推，而要考虑的字符数小于 2n。
但我的疑问是我们为什么不选择前 3 个字符，然后选择 9... 等等。为什么只考虑 2 个字符，因为字符串是相同字符串的一部分，而不是不同的随机字符串？
问问题
556 次
3 回答
6
后缀数组构造算法我还没有分析透彻，但还是想分享一下我的想法。
在我看来，您的问题类似于以下问题：
为什么计算机使用信息的二进制编码而不是三进制？
为什么二进制搜索将范围二等分而不是三等分？
为什么有两种性别而不是三种性别？
原因是数字 2 很特殊——它是最小的复数。1 和 2 之间的差异是定性的，而 2 和 3（以及任何其他正整数）之间的差异是定量的，因此没有那么大。
结果，许多算法和数据结构的二进制公式被证明是最简单的公式，尽管其中一些可能被推广，并增加了不同程度的复杂性，用于任意基础。
于 2016-07-19T15:41:18.290 回答
2
答案是从您链接的帖子中给出的。正如@Leon 回答的那样，该算法之所以有效，是因为它使用二分法来解决排序问题。如果您正确阅读答案，主要目的是将单词分成小的2个字符片段。这样4个字符可以很容易地根据2对字符的排列进行排序，6个字符有4-2或2-4或2-2-2等等。因此，表中包含 3 个字母的单词是无意义的，因为可以看到 3 个字符的单词有 2 个字符 + 最后一个字符在字母表中的位置。
于 2016-07-21T08:43:23.037 回答
2
我认为您只考虑速度2^x与3^x您显然更喜欢后者的速度。但是您必须考虑每一步所需的努力。由于3^x需要的步数比2^x您计算单个步长所需的步数少约3^x1.58 倍，因此您需要在不到 1.58 倍的时间内实现2^x更好的增长。通常，当您必须在每个步骤中处理三个元素而不是两个元素时，问题会变得更加复杂。此外，如果你可以将它扩展到3^x你也可以做得更大n^x，然后随着大n你的算法突然不是指数的，而是有效的线性。
于 2016-07-21T09:18:47.050 回答