数组扩展的效率

2017-11-04

算法

细节

数组扩展的效率差异#

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

本文是我在阅读

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

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

原始代码#

1
template<class T>
2
void arrayList<T>::insert(int theIndex, const T& theElement)
3
{// Insert theElement so that its index is theIndex.
4
   if (theIndex < 0 || theIndex > listSize)
5
   {// invalid index
6
      ostringstream s;
7
      s << "index = " << theIndex << " size = " << listSize;
8
      throw illegalIndex(s.str());
9
   }
10

11
   // valid index, make sure we have space
12
   if (listSize == arrayLength)
13
      {// no space, double capacity
14
         changeLength1D(element, arrayLength, 2 * arrayLength);
15
         arrayLength *= 2;
16
      }
17

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

22
   element[theIndex] = theElement;
23

24
   listSize++;
25
}

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

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

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

背后原理#

这就要用的数学知识了

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

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

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

数组每次增加 1 的情况#

如果数组每次增加 1，那么增加数组长度的时间为 $\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)。

数组每次翻倍的情况#

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

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

$\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)}$

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

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

推论#

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

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

数组扩展的效率

https://blog.dccif.top/2017/11/04/数组扩展的效率/

作者

Barry He

发布于

2017-11-04

许可协议

CC BY-NC-SA 4.0

博客的一键部署

Ubuntu的个性化配置