В чем разница между сортировкой строк и сравнением строк. Разве они не то же самое, что мы должны сравнивать строку, чтобы отсортировать ее?

Question

Предположим, у нас был алгоритм, который принимал массив строк, сортировал каждую строку, а затем сортировал полный массив. Какой будет среда выполнения?

Я немного запутался в решении. В 3-й строке написано Sorting each string is O(s lo g s), В 5-й строке написано Each string comparison takes 0(s ) time. Как я понимаю, даже для сортировки строки мы должны сначала сравнить ее, поэтому не они одно и то же. Почему время выполнения отличается?

• Let S be the length of the longest string.
• Let a be the length of the array.
Now we can work through this in parts:
• Sorting each string isO(s lo g s),
• We have to do this for every string (and there are a strings), so that's 0( a* s lo g s).
• Now we have to sort all the strings. There a re a strings, so you'll may be inclined to say that this takes 0( a
l o g a) time. This is what most candidates would say. You should also take into account that you need
to compare the strings. Each string comparison takes 0(s ) time.There are 0( a lo g a) comparisons,
therefore this will takeO(a* s lo g a)time .
If you add up these two parts, you get 0(a*s ( lo g a + lo g s)) . 

Answer 1

Шаг за шагом

Сравнение Давайте сравним две строки. Чтобы завершить сравнение (в худшем случае), каждая буква одной строки должна сравниваться с каждой буквой другой. Таким образом, здесь сложность O (s), где S - длина строк (учитывая, что они имеют одинаковую длину)

Sorting Now, возьмите одну строку и попробуйте отсортировать ее. Чтобы отсортировать строку, каждый Буква строки длины N должна сравниваться с остальными (N-1) буквами той же строки. Итак, для одного письма вы делаете N-1 сравнения. Поэтому, если вы продолжите это делать, вы выполните (N-1) + (N-2) (поскольку мы уже отсортировали 1 символ до этого) + (N-3) + ... 1 сравнений. Обратите внимание, что это сумма N натуральных чисел, приблизительно равных n (n + 1) / 2 =>, поэтому сложность составляет O (N ^ 2)

Алгоритмы типа быстрой сортировки, сортировки слиянием и т. Д. c , склонны оптимизировать это решение, чтобы довести его до O (N log n)

Возвращаясь к вашему вопросу,

В 5-й строке написано Каждое сравнение строк занимает 0 (s) времени , Это связано с тем, что при сортировке одной строки ваше сравнение по одной букве занимает только O (1) (сравнение одного алфавита с другим). Здесь вы сортируете массив строк КАЖДОЙ длины S (поэтому вам нужно сравнить 2 строки длины S) и это не O (1)

Answer 2

Здесь сортируются две вещи: сначала сортируется каждая строка. Я так понимаю, это означает, что символы строки расположены по порядку. Для этого нам не нужно сравнивать строки, нам нужно сравнивать символов . Сравнение двух символов: O (1) , поэтому сортировка одной строки: O (s log s) (где s - длина строки), что мы должны повторить a раз.

После этого мы сортируем массив отсортированных строк. Для этого нам нужно сравнить строки. Две строки могут отличаться только последним символом, поэтому мы должны просмотреть строки, чтобы сравнить их. Это означает, что сравнение двух строк равно O (s) (где s - длина строки). У нас есть O (log a) сравнений, поэтому умножение этих двух дает сложность O (s * a log a) для сортировки массива строк.

Объединение этих сложностей дает сложность в решении.

Answer 3

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

Но для сравнения вы сравниваете 0-й элемент затем 1-й элемент ... n-й элемент, чтобы выяснить разницу.