1
整数の配列の次の辞書順列（例：123,132,213,231,312,323）を計算するアルゴリズムを作成しました。私はコードが必要だと思っていないが、私はそれを以下に含めた。会計方法を使用して償却された時間コスト
私はO（n）の最悪の場合の時間コストを適切に決定したと思います。ここで、nは配列内の要素の数です。しかし、あなたが "償却コスト"を利用する場合、時間コストは平均的にO（1）として正確に表示されることがわかります。
質問：
私はOとしてこれを表示するには、「会計の方法」を学びたい（1）が、各操作にコストを適用する方法を理解する難しさを持っています。課金方法：Link: 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;
} //スワップにおける実行時間端getNextを