我先说一下数组版的动态数组的摊销分析
我先上C++的代码【没有摊销的】吧
【应该都能看懂吧】【即使没学过C和C++】
#pragma once
#include <iostream>
using namespace std;
#define InitSize 10 //顺序表默认的初始长度
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; //顺序表的当前的最大容量
int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义（动态分配方式）
// 初始化表。构造一个空的线性表L，分配内存空间。
void InitList(SeqList &L)
{
L.data = (int*)malloc(InitSize*sizeof(int));
L.length = 0;
L.MaxSize = InitSize;
// 规范使用就可以避免垃圾值
// 用函数赋值
return;
}
void IncreaseSize(SeqList &L,int len)//当len是1的时候
{
int* p = L.data;
L.data = (int*)malloc((L.MaxSize+len)*sizeof(int));
for(int i = 0;i<L.length;i++)
{
L.data[i] = p[i];
}
L.MaxSize = L.MaxSize+len;
free(p);
return;
}
当你创建了一个可以存储上限10个元素的数组时，想要添加第11个数组时，就需要申请新的空间，使用for将原数组的值复制到新数组，然后再释放原数组，这样for里面的执行语句（不包括for里面的判断语句)那么执行了10次
假设我每次增加的数组长度都是1呢？？
从1上限变为n上限呢？？
那么总的时间是多少呢
1，2，3，4，5...100...1000...n
这是一个等差数列，由等差数列求和公式得出，最后的时间复杂度是指数级的n的平方
这是我们要避免的
那我就要每次增加多少长度呢？？
要按几何增长（可以粗略理解为和n（n就是当前的长度上限）有关的增长，比如每次增加的长度都是n，注意n是变量）
如果我每次增加的长度都是当前的长度n呢？？
那么总时间复杂度会是怎么样呢
python动态数组和摊销分析_zhisuihen6347的博客-CSDN博客_python动态数组
大小按几何增长
假如当前底层数组大小为c，当底层数组存满时，系统创建新的底层数组，其大小为2c（c的倍数）。我们能够证明这样的机制摊销运行时间为O ( 1 ) O(1)O(1)，证明如下：
我们假设底层数组初始大小为c，每次增长原来底层数组的2倍。第一次添加c个元素，其时间复杂度为O ( c ) O(c)O(c)，再添加c个元素，其时间复杂度为O ( 2 c ) O(2c)O(2c)（底层数组满时，需要创建数组并将原来的数据存入新数组，时间复杂度为O ( c ) O(c)O(c)，再加上之后添加的c个元素，其时间复杂度为O ( 2 c ) O(2c)O(2c)），再添加2c个元素，其时间复杂度为O ( 4 c ) O(4c)O(4c)，再添加8c个元素，其时间复杂度为O ( 16 c ) O(16c)O(16c)，以此类推。
