Амортизированная сложность std:: next_permutation?

Ответ 1

Похоже, я собираюсь ответить на свой вопрос утвердительно - да, next_permutation работает в O (1) амостатированном времени.

Прежде чем перейти к формальному доказательству этого, быстро перейдем к тому, как работает алгоритм. Во-первых, он сканирует назад от конца диапазона к началу, идентифицируя самую длинную смежную уменьшающуюся подпоследовательность в диапазоне, который заканчивается на последнем элементе. Например, в 0 3 4 2 1 алгоритм идентифицирует 4 2 1 как эту подпоследовательность. Затем он смотрит на элемент прямо перед этой подпоследовательностью (в приведенном выше примере 3), затем находит наименьший элемент в подпоследовательности, большей, чем он (в приведенном выше примере, 4). Затем обменивается позициями этих двух элементов, а затем меняет указанную последовательность. Итак, если мы начали с 0 3 4 2 1, мы заменили бы 3 и 4, чтобы получить 0 4 3 2 1, и затем перевернем последние три элемента, чтобы получить 0 4 1 2 3.

Чтобы показать, что этот алгоритм работает в амортизированном O (1), мы будем использовать метод потенциала. Определить & Phi; в три раза больше длины самой длинной смежно уменьшающейся подпоследовательности в конце последовательности. В этом анализе мы будем предполагать, что все элементы различны. Учитывая это, подумайте о времени выполнения этого алгоритма. Предположим, что мы сканируем назад от конца последовательности и обнаруживаем, что последние m элементов являются частью уменьшающейся последовательности. Для этого требуется сравнение m + 1. Затем мы найдем элементы этой последовательности, один из которых является наименьшим, большим, чем элемент, предшествующий этой последовательности. Это занимает наихудшее время, пропорциональное длине уменьшающейся последовательности, используя линейное сканирование для других m сравнений. При замене элементов требуется, скажем, 1 кредитная оценка времени, а для изменения последовательности требуется не более т операций. Таким образом, реальное время выполнения этого шага составляет примерно 3m + 1. Однако мы должны учитывать изменение потенциала. После того, как мы отменим эту последовательность длины m, мы заканчиваем тем, что уменьшаем длину самой длинной убывающей последовательности в конце диапазона до длины 1, так как обратное уменьшение последовательности в конце делает последние элементы диапазона отсортированными в порядке возрастания, Это означает, что наш потенциал изменился с & Phi; = 3 м до & Phi; ' = 3 * 1 = 3. Следовательно, чистое падение потенциала составляет 3 - 3 м, поэтому наше чистое амортизированное время равно 3m + 1 + (3 - 3m) = 4 = O (1).

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

Ответ 2

Я не уверен в точности реализации std:: next_permutation, но если он такой же, как алгоритм Нараяны Пандиты, как описано в wiki здесь: http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations,

предполагая, что элементы различны, похоже, что O (1) амортизируется! (Конечно, могут быть ошибки ниже)

Давайте посчитаем общее количество выполненных свопов.

Получаем рекуррентное соотношение

T (n + 1) = (n + 1) T (n) + & Theta; (n ²)

(n + 1) T (n) происходит от фиксации первого элемента и выполнения свопов для оставшихся n.

& Theta; (n ²) происходит от изменения первого элемента. В точке мы меняем первый элемент, мы делаем & Theta; (n) свопами. Сделайте это n раз, вы получите & Theta; (n ²).

Теперь давайте X(n) = T(n)/n!

Тогда получим

X (n + 1) = X (n) + & Theta; (n ²)/(n + 1)!

i.e существует некоторая константа C такая, что

X (n + 1) <= X (n) + Cn ²/(n + 1)!

Записывая n таких неравенств, мы получаем

X (n + 1) - X (n) <= Cn ²/(n + 1)!

X (n) - X (n-1) <= C (n-1) ²/(n)!

X (n-1) - X (n-2) <= C (n-2) ²/(n-1)!

...

X (2) - X (1) <= C1 ²/(1 + 1)!

Добавление этих значений дает нам X(n+1) - X(1) <= C(\sum j = 1 to n (j^2)/(j+1)!).

Так как бесконечный ряд \sum j = 1 to infinity j^2/(j+1)! сходится к C ', скажем, получаем X(n+1) - X(1) <= CC'

Помните, что X (n) подсчитывает среднее количество необходимых свопов (T (n)/n!)

Таким образом, среднее число свопов равно O (1).

Так как поиск элементов для swap является линейным с числом свопов, то O (1) амортизируется, даже если вы принимаете во внимание другие операции.

Ответ 3

Здесь n обозначает количество элементов в контейнере, а не общее количество возможных перестановок. Алгоритм должен перебирать порядок всех элементов при каждом вызове; он берет пару двунаправленных итераторов, что подразумевает, что для перехода к одному элементу алгоритм должен сначала посетить тот, который был перед ним (если только его первый или последний элемент). Двунаправленный итератор позволяет итерации назад, поэтому алгоритм может (должен, по сути) выполнять вдвое меньше свопов, чем есть элементы. Я считаю, что стандарт может предложить перегрузку для итератора, который будет поддерживать итераторы dumber за счет n свопов, а не половинных свопов n. Но, увы, это не так.

Конечно, для n возможных перестановок алгоритм работает в O (1).