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

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

0 голосов
/ 27 мая 2019

Вопросы:

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

Решение дано ниже: enter image description here

Что я нахожу особенным в приведенном выше решении, так это: "You should also take into account that you need to compare the strings. Each string comparison takes O (s) time.There are O (a log a) comparisons, therefore this will take O (a*s log a) time."

Для чего нам нужны сравнения?

Потребуется s log s время для сортировки строки. Скажем, a строк, следовательно, общее время будет a*s log s

Теперь проблема сократилась до простой сортировки заданного массива, которую вы можете сделать за a log a времени, следовательно, общее время, которое вы взяли a*s log s + a log a = a (s log s + log a)

Где я ошибся в своем мыслительном процессе?

Вопрос взят из книги, Взлом Интервью Кодирования

1 Ответ

1 голос
/ 27 мая 2019

Сортировка списка чисел предполагает, что сравнения происходят за O (1) постоянного времени, что дает сложность nlogn с точки зрения количества сравнений. Однако, когда мы сортируем перечислимое, членам которого для сравнения требуется время x, время выполнения становится xnlogn. Это потому, что мы выполняем действие, которое требует x времени, nlogn раз.

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

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

В противном случае сортировка обычно занимает (время сравнения) x nlogn

...