Похоже, что я собираюсь ответить на свой собственный вопрос утвердительно - да , 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 кредитное время, а для изменения последовательности требуется не более m операций. Таким образом, реальное время выполнения этого шага составляет примерно 3 м + 1. Однако мы должны учитывать изменение потенциала. После того, как мы изменим эту последовательность длины m, мы в конечном итоге уменьшим длину самой длинной убывающей последовательности в конце диапазона до длины 1, потому что обратная последовательность уменьшения в конце делает последние элементы диапазона отсортированными в порядке возрастания , Это означает, что наш потенциал изменился с & Phi; = 3 м до & Phi; ' = 3 * 1 = 3. Следовательно, чистое падение потенциала составляет 3–3 м, поэтому наше амортизированное время составляет 3 м + 1 + (3–3 м) = 4 = O (1).
В предыдущем анализе я сделал упрощающее предположение, что все значения являются уникальными. Насколько мне известно, это предположение необходимо для того, чтобы это доказательство сработало. Я собираюсь обдумать это и посмотреть, можно ли изменить доказательство, чтобы оно работало в случае, когда элементы могут содержать дубликаты, и я опубликую правку этого ответа, как только проработаю детали.