Я изучал создание массивов суффиксов, и я понимаю, что мы сначала сортируем все суффиксы в соответствии с первым символом, затем согласно первым двум символам, затем первые 4 символа и т.д., в то время как число символов, подлежащих рассмотрению, меньше, чем 2n.
Но я сомневаюсь, почему мы не выбираем первые 3 символа, затем 9... и так далее. Почему учитываются только 2 символа, поскольку строки являются частью одних и тех же строк, а не разных случайных строк?
Я не полностью проанализировал алгоритм построения массива суффикса, но все равно хотел бы поделиться своими мыслями.
По моему скромному мнению, ваш вопрос похож на следующие:
Почему компьютеры используют двоичное кодирование информации вместо тройного?
Почему двоичный поиск делит пополам диапазон вместо того, чтобы trisecting его?
Почему существуют два пола, а не три?
Причина в том, что номер 2 является особенным - это наименьшее число множественных чисел. Разница между 1 и 2 является качественной, тогда как разница между 2 и 3 (а также любое другое положительное целое число) является количественной и, следовательно, не столь резкой.
В результате двоичная формулировка многих алгоритмов и структур данных оказывается самой простой, хотя некоторые из них могут быть обобщены с различной степенью сложности для произвольной базы.
Ответ предоставляется из сообщения . И как ответил @Leon, алгоритм работает, потому что использует дихотомический подход для решения проблемы сортировки. если вы правильно прочитали ответ, основная цель - разделить слово на небольшие фрагменты с 2 символами. Так что 4 символа могут быть легко отсортированы по расположению двух пар символов, 6 символов с 4-2 или 2-4 или 2-2-2 и так далее. Таким образом, слово из 3 букв в таблице не имеет смысла, так как может отображаться слово из 3 символов, имеет 2 символа + позицию в алфавите последнего символа.
Я думаю, что вы рассматриваете только скорость 2^x по сравнению с 3^x, где вы, очевидно, предпочтете последнее.
Но вы должны учитывать усилия, необходимые для каждого шага.
Поскольку 3^x требуется примерно на 1,58 меньше шагов, чем 2^x, вам нужно будет вычислить один шаг для роста 3^x менее чем в 1,58 раза, что вам нужно для одного шага роста 2^x для выполнения лучше.
Как правило, проблемы будут намного сложнее, если вам придется обрабатывать три элемента на каждом шаге, а не два.
Кроме того, если вы могли бы расширить его до 3^x, вы могли бы также сделать это для большего n^x, а затем с большим n ваш алгоритм внезапно не экспоненциальный, а эффективно линейный.