雙陣列隊列add（i，x）的運行時間

DualArrayDeque表示使用兩個ArrayStacks的列表。雙陣列隊列add（i，x）的運行時間

List<T> front; 
List<T> back; 

void add(int i, T x) { 

    if (i < front.size()) { 
     front.add(front.size()-i, x); 
    } else { 
     back.add(i-front.size(), x); 
    } 

    balance(); 

}

忽略balance（）的運行時間。如果i < front.size()，add(i,x)運行時間是O(i+1)。將0-i元素向左移[O(i)]並將第i個元素指定給x [O(1)]。同樣，當i > front.size()，它是O(n-i+1);

front.size()和back.size()相差不超過3倍。特別是，3 · front.size() ≥ back.size()和3 · back.size() ≥ front.size()。因此，如果i < n/4和O(1 + n − i)如果i ≥ 3n/4運行時間是O(1 + i);

我的問題是當n/4 <= i < 3n/4，爲什麼add(i,x)的運行時間是O(n)？

PS：我正在閱讀Open Data Structure http://opendatastructures.org/ods-java/2_5_DualArrayDeque_Building.html。我很困惑，爲什麼它是O(n)。

來源

2017-04-23 Di Wang

我剛剛瀏覽了您所指的文字。你的答案在於balance（）函數。

void balance() { 
    int n = size(); 
    if (3*front.size() < back.size()) { 
     int s = n/2 - front.size(); 
     List<T> l1 = newStack(); 
     List<T> l2 = newStack(); 
     l1.addAll(back.subList(0,s)); 
     Collections.reverse(l1); 
     l1.addAll(front); 
     l2.addAll(back.subList(s, back.size())); 
     front = l1; 
     back = l2; 
    } else if (3*back.size() < front.size()) { 
     int s = front.size() - n/2; 
     List<T> l1 = newStack(); 
     List<T> l2 = newStack(); 
     l1.addAll(front.subList(s, front.size())); 
     l2.addAll(front.subList(0, s)); 
     Collections.reverse(l2); 
     l2.addAll(back); 
     front = l1; 
     back = l2; 
    } 
}

當3 * front.size（）< back.size（），平衡（）被複制的n/2 front.size（）從回L1元件，扭轉它，複製的所有元素前進到l1並將其餘的元素複製回l2。

類似地，當3 * back.size（）< front.size（），平衡（）由n複製從前方/ 2 + 1到元件L1，複製前的其餘元件進入L2，扭轉它和複製所有後面的元素也變成了l2。

在上述兩種情況下，balance（）函數會將前後所有元素複製到l1和l2中，這會花費O（n）個時間。

來源

2017-04-23 18:21:19 iavanish

考慮在兩個支持陣列之間發生3n/4位置分裂的情況。所以前面陣列有3n/4個元素，後面陣列有n/4個元素。現在當有人打電話給add（i）時發生了什麼，其中i = 3n/4-1。也就是說，當某人添加到前面數組的最後一個元素時會發生什麼。由於前面的數組堆棧實際上是相反的，就像在數組堆棧中向索引0添加數據一樣：該堆棧中的所有內容都必須移位一個以騰出空間。所以最壞的情況下，如果n/4我們可以移動3n/4個元素，即O（n）。

來源

2017-07-07 22:00:56 Andrew

雙陣列隊列add（i，x）的運行時間

回答

相關問題