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。由于每次迭代最多一次交换是昂贵的，因此每次迭代的运行时间是摊销常数（假设我们不负债）。
  3. To show that we don't go into debt, it suffices to show that, if the swap of array[j] and array[k] leaves a credit at position j, then every other swap involves a position with a credit available, which is consumed. Case analysis and induction reveal that, between iterations, if an item is larger than the one immediately following it, then it was put in its current position by a swap that left an as-yet unconsumed credit.
  4. This problem is not a great candidate for the accounting method, given the comparatively simple potential function that can be used: number of indexes j such that array[j] > array[j + 1].
于 2012-03-05T12:57:22.780 回答
0

From the aggregate analysis, we see T(n) < n! · e < n! · 3, so we pay $3 for each operation, and its enough for the total n! operations. Therefore its an upper bound of actual cost. So the total amortized

于 2012-03-22T02:21:02.443 回答