Я написал алгоритм для вычисления следующей лексикографической перестановки массива целых чисел (например, 123, 132, 213, 231, 312,323).Я не думаю, что код необходим, но я включил его ниже.
Я думаю, что я правильно определил наименьшую стоимость времени O (n), где n - количество элементов в массиве.Однако я понимаю, что если вы используете «Амортизированную стоимость», вы обнаружите, что стоимость времени может быть точно показана в среднем как O (1).
Вопрос:
Я хотел бы узнать«МЕТОД УЧЕТА», чтобы показать это как O (1), но мне трудно понять, как применить стоимость к каждой операции.Метод учета: Ссылка: Accounting_Method_Explained
Мысли:
Я решил применить стоимость изменения значения в позиции или применить стоимость к свопу.Но это действительно не имеет особого смысла.
public static int[] getNext(int[] array) {
int temp;
int j = array.length - 1;
int k = array.length - 1;
// Find largest index j with a[j] < a[j+1]
// Finds the next adjacent pair of values not in descending order
do {
j--;
if(j < 0)
{
//Edge case, where you have the largest value, return reverse order
for(int x = 0, y = array.length-1; x<y; x++,y--)
{
temp = array[x];
array[x] = array[y];
array[y] = temp;
}
return array;
}
}while (array[j] > array[j+1]);
// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]
for (;array[j] > array[k]; k--,count++);
//Swap the two elements found from j and k
temp = array[k];
array[k] = array[j];
array[j] = temp;
//Sort the elements to right of j+1 in ascending order
//This will make sure you get the next smallest order
//after swaping j and k
int r = array.length - 1;
int s = j + 1;
while (r > s) {
temp = array[s];
array[s++] = array[r];
array[r--] = temp;
}
return array;
} // end getNext