Какова сложность времени выполнения после изменения вида слияния

Question

Я безуспешно пытался найти ответ на эту проблему, может быть, вы могли бы немного привести меня: Мы изменили сортировку слиянием, чтобы, когда вы уже отсортировали массив, он останавливался и возвращал массив без вызова другого2 рекурсивных звонка.например, давайте запустим алгоритм для массива, чтобы каждое число в массиве появлялось ровно n / log (n) раз (чтобы массив содержал ровно log (n) разных чисел), какова будет сложность во время выполнения?

Answer 1

"Мы изменили сортировку слиянием, чтобы, когда вы уже отсортировали массив, он останавливался и возвращал массив без вызова еще 2 рекурсивных вызовов."

Так работает нормальная сортировка слиянием. После сортировки массива (или раздела массива) он больше не вызывает рекурсивных вызовов, он просто возвращает отсортированный массив. Рекурсия называется , чтобы отсортировать секцию массива в первую очередь.

Возможно, вы хотели сказать: «Прежде чем мы рекурсивно сортируем 2 половинки и объединяем их, мы проверяем, не отсортирован ли массив». Это было бы бесполезно для массивов с разными номерами, так как была бы крайне низкая вероятность (1/n!) того, что массив будет отсортирован.

На вашем примере это более интересно, однако, если массив имеет только log(n) разных чисел, я бы порекомендовал упорядочить уникальные значения и создать хэш-карту от значения к индексу, что быстро только для значений log(n), а затем вы например, можно сортировать по линейному времени с помощью сортировки по сегментам.

Answer 2

Действительно, вы можете попытаться улучшить эффективность сортировки слиянием для отсортированных массивов, проверив, находятся ли отсортированные подмассивы в правильном порядке, и пропустив фазу объединения.Это может быть эффективно сделано путем сравнения последнего элемента A левого подмассива для первого элемента B правого подмассива.Если A <= B, объединение не требуется.

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

Другой подход заключается в проверке, если массив уже отсортирован за до разбиения и рекурсии.Это добавляет еще много тестов в общем случае, но не увеличивает сложность, так как это количество тестов также ограничено N log (N) .В среднем это дороже для несортированных массивов (больше дополнительных сравнений), но более эффективно для отсортированных массивов (такое же количество тестов, но без рекурсии).

Вы можете попробовать сравнить оба подхода на различных тестовых примерах.и размеры массивов для измерения воздействия.