Предположим, у нас есть алгоритм, который принимает массив строк, сортирует каждую строку, а затем сортирует весь массив. Каким будет время выполнения?
Вопросы:
Предположим, у нас есть алгоритм, который принимает массив строк, сортирует каждую строку, а затем сортирует весь массив. Каким будет время выполнения?
Что я нахожу странным в приведенном выше решении, так это: "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)
Где я ошибся в своем мыслительном процессе?
Вопрос взят из книги Интервью по кодированию
Заявление о том, что «нельзя уменьшить его дальше», кажется, натянуто. Понятно, что тривиальное сравнение строк будет O(s) — но из этого сразу не следует, что сортировка строк в этом случае должна быть реализована именно так.
Ответы 1
Сортировка списка чисел предполагает, что сравнения происходят за O(1) постоянное время, что дает сложность nlogn с точки зрения количества сравнений. Однако, когда мы сортируем перечисляемое, члены которого требуют времени x для сравнения, время выполнения становится xnlogn. Это потому, что мы выполняем действие, которое требует x времени, nlogn раз.
Но я также должен утверждать, что строки являются прямой биекцией по основанию 26. Поскольку мы считаем, что сравнение по основанию 10 происходит за постоянное время, нет причин не распространить это на строки, которые по сути являются числами по основанию 26. Это действительно зависит от реализации механизма сравнения строк. Таким образом, в зависимости от того, как выполняется сравнение строк, мы получаем две возможные среды выполнения.
Вы правы, если и только если мы предполагаем, что строки сравниваются как числа в базе 26, и если это можно сделать за постоянное время.
В противном случае сортировка в целом занимает (время сравнения) x nlogn
Связано: Как мы можем предположить, что основные операции над числами занимают постоянное время? Тот же самый аргумент не применим к строкам.
Сложность сортировки обычно определяется количеством сравнений (по крайней мере, для сортировки на основе сравнений). В этом случае не нужно делать никаких предположений о сложности одного сравнения. Хотя окончательный вывод один и тот же.
Они просят время, а не количество сравнений. Хотя время произвольно, они, кажется, хотят что-то с точки зрения длин отдельных строк. Кроме того, я действительно не понял связанную ссылку, но я не вижу причин для того, чтобы это предположение не применялось к строкам, учитывая реализацию строк в виде массивов символов, которые по сути являются целочисленными массивами, как указано в вопросе
Числа чаще всего имеют длину 64 бита или меньше, и многие операции могут выполняться параллельно и в любом случае проверять или обрабатывать все биты, поэтому время их выполнения часто не зависит от точного количества битов, которое занимает число. Строки, с другой стороны, не имеют общего фиксированного верхнего предела длины, сравнение будет включать проверку одной позиции за раз, а время выполнения очень сильно зависит от точной длины строки. Но может быть некоторое махание руками, поскольку вы не можете, строго говоря, сказать, что число постоянного пространства может представлять длину чего-то, что является переменным пространством.
Понимаю. Предполагая, что строка является числом без верхних границ, тогда мы можем считать ее время сравнения равным (длина/параллельные процессы)?
Обычно сравнение не делается параллельно (насколько мне известно), так что это просто O(length). Вы также можете выполнять сравнение параллельно, если это необходимо, но вам понадобится алгоритм, чтобы узнать время выполнения — вам может потребоваться дополнительное время для сбора результатов от отдельных процессов — это можно сделать в O(log(parallel processes)), объединив 2 процесса за раз , что приведет к времени выполнения O(length/parallel processes + log(parallel processes)).
Хорошо, не стесняйтесь редактировать мой ответ, чтобы обновить его соответствующей информацией! Или опубликуйте этот обмен как самостоятельный ответ
Each string comparison takes O(s) time. Это та часть, которую вы пропустили, рассуждая. Сравнение двухcharзанимаетO(1), сравнение двух строк занимаетO(length(shortest string)).