algorithm - Previous Larger Element 算法的预期运行时间

Question

以下算法返回数组中前一个较大的元素。它来自 these 的第 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} 的随机排列, 预计运行时间是多少？

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

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

Answer 1

基于@Heuster 的回答:

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

2) 元素 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) 之间，所以它似乎是一个很好的候选者:)