Блог

Главная - Вопросы по программированию - измените алгоритм, чтобы получить оптимальное время выполнения

измените алгоритм, чтобы получить оптимальное время выполнения

#arrays #algorithm #sorting #quicksort #partition

Вопрос:

У меня есть алгоритм, который выполняет обратное разделение

 Reverse-Partition(A, p, q, r)
  pivot = A[q]
  j = r
  i = q
   while j ≥ p   1 and i ≥ p
     if A[j] > pivot
      exchange A[j] with A[i]
      i = i − 1
   j = j − 1

Я пытаюсь написать алгоритм, который работает быстрее, чем описанный выше, чтобы получить наиболее оптимальное время выполнения

 Fast-Reverse-Partition(A, p, q, r) 
BEGIN:

For(int i = r; i > (r-q); i--):
   swap A[i] and A[i-(r-q)]

END

В функции обратного разбиения в данном массиве все элементы в индексе q~r все больше, чем элемент pivot, а элементы в индексе p~q все меньше, чем элемент pivot, поэтому я думаю, что с помощью приведенного выше мы можем получить тот же результат, что и функция обратного разбиения.
Эта функция имеет время выполнения n = r-(r-q) 1 = q 1, поэтому она быстрее, чем функция обратного разбиения.
Имеет ли это смысл? или мое понимание неверно?

Комментарии:

1. При выполнении подобной работы рекомендуется создать платформу тестирования, в которой вы сможете постоянно проверять, что ваш алгоритм по-прежнему выполняет то, что он должен делать, когда вы вносите в него изменения.

Ответ №1:

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

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

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

Что касается «оптимального времени выполнения». За это время было изобретено множество схем разделения, большинство из которых пытались оптимизировать одну из следующих:

  • количество сравнений
  • количество свопов
  • поведение в худшем случае (все элементы одинаковы или в строго обратном порядке)
  • удобочитаемость

При понимании конкретной схемы разделения важно понимать, что она пытается оптимизировать, а также какие инварианты она пытается поддерживать (и это может быть очень сложно!).

Я бы рекомендовал начать с тщательного прочтения вики-статьи, она содержит несколько популярных схем разделов с соответствующими компромиссами.

Метки: ,