Докажите, что время выполнения быстрой сортировки после модификации = O (Nk) - PullRequest
Новая
       24

Докажите, что время выполнения быстрой сортировки после модификации = O (Nk)

3 голосов
/ 22 декабря 2011

это вопрос домашнего задания, и я не так стараюсь найти соответствие, но я стараюсь изо всех сил!

  • Трехстороннее разбиение - это модификация быстрой сортировки, которая разбивает элементы на группыменьше, равно и больше, чем стержень.Только группы меньших и больших элементов должны быть рекурсивно отсортированы.Покажите, что если имеется N элементов, но только k уникальных значений (другими словами, существует много дубликатов), то время выполнения этой модификации быстрой сортировки равно O (Nk).

my try:

в среднем случае:

подпрограммы дерева будут иметь следующие индексы:

Я предполагаю, что подпрограмма с дублирующимися элементами будет равна (nk)

  • первый: от 0 - до (i-1)
  • второй: i - (i + (nk-1))
  • третий: (i + nk) - (n-1)
  • количество сравнений = (nk) -1

Итак, 

T(n) = (n-k)-1 + Sigma from 0 until (n-k-1) [ T(i) + T (i-k)]

тогда я не уверен, как я буду продолжать:S

Хотя это может быть очень плохое начало: $ Надеюсь найти помощь

Ответы [ 2 ]

5 голосов
/ 22 декабря 2011

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

Вы должны посмотреть на максимально возможную глубину рекурсии. При обычной быстрой сортировке максимальная глубина составляет n. Для каждого уровня общее количество выполненных операций равно O(n), что в худшем случае дает O(n^2) всего.

Здесь нетрудно доказать, что максимально возможная глубина равна k (так как одно уникальное значение будет удалено на каждом уровне), что приводит к O(nk) итого.

3 голосов
/ 22 декабря 2011

У меня нет сложного формального образования.Но если вы думаете об этом как о математической проблеме, вы можете доказать это как математическое доказательство.

Для всех алгоритмов сортировки лучший сценарий всегда будет O (n) для n элементов, потому что для сортировки n элементов вы должны рассмотреть каждый из них как минимум один раз.Теперь, для вашей конкретной оптимизации быстрой сортировки, вы упростили проблему, потому что теперь вы сортируете только уникальные значения: все значения, которые совпадают с сводной, уже считаются отсортированными, и в силу своей природы быстрая сортировкабудет гарантировать, что каждое уникальное значение будет отображаться как опорная точка в некоторый момент операции, поэтому это устраняет дубликаты.

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

Подводя итог:

  • Этот алгоритм исключает проверку на повторяющиеся значения.
  • Но все алгоритмы сортировки должны смотреть на каждое значение в списке хотя бы один раз. N операций
  • Для каждого значения в списке операция должна найти свою позицию относительно других значений в списке.
  • Поскольку удаляются дубликаты, остается только k значения для сравнения.
  • O (Nk)
...