выполнения двойного алгоритма

Question

сортировочной В этой картине, у меня возникают проблемы с пониманием, почему сортировки сортировки массива требует понимания того, что «Каждое сравнение строк занимает O времени (s)», поэтому умножение на * (журнал секция. Почему сравнение строк в непостоянное время? У меня возникли проблемы с концептуализацией этого.

В качестве продолжения наш подход умножения на s аналогичен тому, почему для сортировки строки требуется s log (s) в отличие от log (s)? Является ли дополнительное «s» в «сортировке каждой строки O (s log (s))« результатом сравнения символов внутри строки (в отличие от сравнения целых строк друг с другом в массиве)? Извините, если это не имеет большого смысла, но для меня это путаница.

Answer 1

Думаю, вы смешали две вещи. Сортировка одной строки длины s принимает O (s log s).

Для сравнения двух строк s1, s2 они могут быть произвольными большими, и мы не можем поместить их в любой регистр для сравнения их в O (1), поэтому нам нужно O (| s1 | + | s2 |) для времени сравнения сравнить их по характеру. На картинке автор предположил, что самая длинная строка имеет длину не более s.

Answer 2

Учитывая две строки (например, байты), каждая из которых имеет длину s, их можно сравнить в любом случае, чтобы пройти через префиксную строку, общую для обеих строк, чтобы найти первое различие. Для двух случайных строк средняя длина общего префикса p составляет приблизительно 1/256, независимо от длины строки, поэтому сравнение будет O(1).

Однако, это отсортировано по номеру строки. Если строки были случайными для начала, после сортировки каждый из них начинает с нуля s/256 нулевых байтов, которые необходимо отсканировать (для этого вероятность того, что у них одинаковое количество нулевых байтов, ничтожно мала, поэтому мы надеваем не нужно беспокоиться об остальном), поэтому сравнение отсортированных строк заканчивается O(s). (Отредактировано с исправлением: на самом деле, если строковое представление может предоставить длину в постоянное время, я думаю, вы можете использовать двоичный поиск для сравнения отсортированных строк.)

С другой стороны, мы говорим о сравнении строки в контексте сортировки, и мне не совсем ясно, что мы можем предположить, что временная сложность операций сравнения , имевшая место в контексте сортировки, обязательно будет продуктом O(s) для каждого сорта, умноженного на ожидаемый количество сравнений, так как среднее сходство сравниваемых строк (как измерено их общим префиксом), вероятно, будет увеличиваться в ходе сортировки.

В результате, я подозреваю, что это можно вычислить временную сложность в размере струн для фиксированной количество строк и наоборот, используя аргумент выше, но я не так уверен в совместной сложности времени в s и a хранится на всех возможных путях, чтобы s и a могли перейти в безразличие.