0

以下算法返回数组的前一个较大元素。它来自这些注释的第 11 页。

// Input: An array of numeric values a[1..n]
// Returns: An array p[1..n] where p[i] contains the index of the previous
// larger element to a[i], or 0 if no such element exists.
previousLarger(a[1..n]) 
    for (i = 1 to n)
        j = i-1;
        while (j > 0 and a[j] <= a[i]) j--;
        p[i] = j;
return p

我的作业问题是：给定输入序列{a1,...,an}是集合的随机排列，{1,...,n}预期的运行时间是多少？

我认为这需要某种概率分析，但我需要一些提示，因为我过去只做过最坏情况分析。我试图找到j-loop给定 i 的成本公式（1 + 我们执行操作的次数j--），然后将该公式从 1 加到 n。

“预期”是什么意思？我真的不知道如何解释这个。

4

2 回答 2

1

基于@Heuster 的回答：

1) 你知道答案在 O(n) 和 O(n^2) 之间。这只是为了检查最终结果。

2) element 的预期步骤数i确实是：

sum_{k=1}^i 1 / (k+1)
= O(log i)

3）你必须把所有这些数字加到 i 上。这给了你：

sum_{i=1}^n O(log i)
= O(n log n)

我所做的一点也不严谨，但你可以证明它是推导出来的。O(n log n) 介于 O(n) 和 O(n^2) 之间，因此它似乎是一个不错的候选者:)

于 2013-09-29T17:21:41.607 回答
0

对于和任意索引i，有什么机会a[i-1] > a[i]（换句话说，内部 while 循环将采取一步）？这很简单：所有元素a都不同，所以P(a[i-1] > a[i]) = P(a[i] > a[i-1]) = 1/2.

现在，看看内部 while 循环需要采取两个步骤的情况。即，a[i-2] > a[i] > a[i-1]。这正是 3 个元素的 6 个排列之一，所以机会是1 / 3! = 1 / 6。

让我们概括一下，并假设内部 while 循环需要采取k措施。我们考虑 sublist a[i-k], a[i-k+1], ..., a[i]。我们知道这a[i-k]是这个子列表的最大元素和a[i]第二大元素（否则，内部循环会更快停止）。两者之间的元素顺序无关紧要。我们采取k措施的机会就是这样1 / (k + 1) * 1 / k = 1 / (k * (k + 1))。请注意，这确实可以概括为1/2fork = 1和1/6for k = 2。

之前没有元素a[i]更大的机会很简单1 / i（a[i]是该子列表中的最大元素）。在这种情况下，内部循环将需要i步骤。

元素的预期步数i将是（概率乘以值的总和）：

Sum[{k, 1, i} k * 1 / ((k * (k + 1))] + i / i 
    = Sum[{k, 1, i} 1 / (k + 1)] + 1
    = H_{i+1}

其中H_{i}是第 i 个谐波数，它是 的离散变体log i。也就是说，元素的步数i是Θ(i)。

现在剩下的是总和i以找到预期的运行时间。使用确切的值 ( H_{i+1}) 这不会导致很好的表达式，请参阅Wolfram Alpha。

然而，进行的标准方法是继续使用近似的log i. 显然，log 0 + log 1 + ... + log n-1小于n log n。现在，考虑总和的后半部分：

log n/2 + log n/2+1 + ... + log n-1 > n/2 log n/2
                                    = n/2 (log n - log 2)
                                    = Ω(n log n)

因此，预期运行时间为Θ(n log n)。

于 2013-09-29T12:59:41.847 回答