算法--均摊分析时间复杂度

  在数据结构这门课,老师讲到实现动态顺序存储方式。给出了一个最好的办法:将数组扩大一倍,复制过去。
   具体来说。以数组为例,我们都知道初始化一个数组,需要给数组规定一个大小。因为数组的大小是固定的,一旦元素超过了数组的固定大小,就会产生错误。这时我们需要开辟一个新的空间,假设原来数组大小是X,则新开辟空间的大小是2X。将原来的数据复制到新的空间。原来的空间释放掉。

经过四次空间扩大
  这里就会出现均摊时间复杂度。我们知道,假设n个数据,此时复制操作的时间复杂度是O(n)。因为是扩大了一倍,此时整个数组的大小是2n,我们还可以再继续存放n个数据。数组插入的时间复杂度是O(1),只有剩余的n个空间全部插入数据才会开辟新的空间。
  开辟空间时间复杂度是O(n),而执行完n次插入数据才会再继续开辟空间,插入数据的时间复杂度是O(1),这n次插入数据操作平分开辟空间O(n)的时间复杂度,所以每次插入数据的时间复杂度都是O(1)。这就是均摊时间复杂度。
  C++中的vector(向量)就是这种方式实现动态的数组。