以前的較大元素算法的預期運行時間

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}的隨機排列，什麼是預期的運行時間？

我認爲這需要某種概率分析，但我需要一些提示，因爲我以前只做過最壞情況分析。我試圖找到j-loop對於給定的i（1 +我們操作的次數j--）的成本公式，然後將該公式從1增加到n。

「預期」是什麼意思？我真的不知道如何解釋這一點。

Answer 1

對於任意索引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。

讓我們概括一下，並假設inner while循環將需要採取k步驟。我們考慮子列表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/2的k = 1和1/6的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)。

Answer 2

大廈@ Heuster的回答是：

1）你知道，答案是O（n）和O（N^2之間）。這只是爲了檢查最終結果。

2）的步驟元素i預期的數量確實是：

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

3）你必須在總結我所有的號碼。這給你：

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

我所做的並不嚴格，但你可以證明派生它。 O（n log n）在O（n）和O（n^2）之間，所以它似乎是一個很好的候選:)