2

整数の配列 (例: 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;

} // getNext を終了します

4

2 に答える 2

1
  1. 反復ごとの他の作業は最悪の場合のO（#swaps）であるため、スワップの実行時間を測定します。
  2. array[j]とのスワップのarray[k]仮想コストは2です。他のスワップの仮想コストは0です。反復ごとに最大で1つのスワップにコストがかかるため、反復ごとの実行時間は一定に償却されます（債務を負わないと仮定）。
  3. array[j]債務を負わないことを示すには、スワップしてクレジットをポジションにarray[k]残す場合、j他のすべてのスワップには、利用可能なクレジットのあるポジションが含まれ、それが消費されることを示すだけで十分です。ケース分析と誘導により、反復の間に、アイテムがその直後のアイテムよりも大きい場合、そのアイテムは、まだ消費されていないクレジットを残したスワップによって現在の位置に置かれたことが明らかになります。
  4. 使用できる比較的単純な潜在的な関数を考えると、この問題は会計方法の優れた候補ではありませjんarray[j] > array[j + 1]。
于 2012-03-05T12:57:22.780 に答える
0

集計分析から、T(n) < n! · e < n! · 3 なので、各操作に 3 ドルを支払います。合計 n には十分です。オペレーション。したがって、実際のコストの上限です。したがって、償却された合計

于 2012-03-22T02:21:02.443 に答える