数组扩展的效率

发表于 更新于 分类于 本文字数： 633 阅读时长 ≈ 2 分钟

数组扩展的效率差异

说来惭愧，我现在才开始认真的学习算法和程序的效率 😓。

本文是我在阅读

Data Structures,Algorithms,and Applications in C++ Second Edition
Sartaj Sahni

遇到的一个小细节，与数组扩展的效率差异的原理。

原始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement)
{// Insert theElement so that its index is theIndex.
   if (theIndex < 0 || theIndex > listSize)
   {// invalid index
      ostringstream s;
      s << "index = " << theIndex << " size = " << listSize;
      throw illegalIndex(s.str());
   }

   // valid index, make sure we have space
   if (listSize == arrayLength)
      {// no space, double capacity
         changeLength1D(element, arrayLength, 2 * arrayLength);
         arrayLength *= 2;
      }

   // shift elements right one position
   copy_backward(element + theIndex, element + listSize,
                 element + listSize + 1);

   element[theIndex] = theElement;

   listSize++;
}

不知道各位有没有觉得奇怪，为什么12-16行是当空间不足的时候，数组空间翻倍呢？

同样的问题书上也提供了解答。。。。不过也许是我数学基础太差了，一时半会没理解 😥

本文也参考了Stack Overflow上的Efficiency of growing a dynamic array by a fixed constant each time?

背后原理

这就要用的数学知识了

让我们假设现在有一个初始长度为 1 的空数组，需要执行 n=2k+1n=2^k+1

n 次的插入操作，每次都在尾部插入。

于是，每次插入我们都不需要移动已经存在的元素，n 次插入的时间是 Θ(n)加上数组扩展长度的时间。

数组每次增加 1 的情况

如果数组每次增加 1，那么增加数组长度的时间为

Θ(∑i=1n−1i)=Θ(1+2+3+4+...+(n−1))=Θ(n(n−1)2)=Θ(n2)\Theta (\sum _{i=1}^{n-1} i)=\Theta(1+2+3+4+...+(n-1))=\Theta(\frac{n(n-1)}{2} )=\Theta(n^2)

利用等差数列的公式，得到，如果数组每次长度增加 1，n 次插入的总时间是 Θ(n^2)。

数组每次翻倍的情况

下面来解释为什么原始代码中的数组扩展使用的翻倍

如果数组长度每次增倍，那么改变数组长度的时间是

Θ(∑i=0k2i)=Θ(20+21+22+...+2k)=Θ(2k+1−1)\Theta(\sum _{i=0}^k 2^i)=\Theta(2^0+2^1+2^2+...+2^k)=\Theta(2^{k+1}-1)

k=log⁡2(n−1)k={\log _2(n-1)}

Θ(2k+1−1)=Θ(2log⁡2(n−1)+1−1)=Θ(2n−3)=Θ(n)\Theta(2^{k+1}-1)=\Theta(2^{\log _2(n-1)+1}-1)=\Theta(2n-3)=\Theta(n)

利用等比数列公式，得到，如果每次数组长度翻倍，n 次插入的总时间是 Θ(n)。

推论

从数组每次翻倍的情况的公式，我们可以看出如果我们总是在原数组上按一个乘法因子来倍增，得到的总时间都是是 Θ(n)

这也是为什么原始代码中使用的是把长度翻倍的原因。