双阵列队列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）的运行时间

回答

相关问题