数据结构基础：顺序表

文章目录

顺序表python 中顺序表存储的两种基本形式： 顺序表的表现形式python中顺序表的扩充 顺序表的效率

顺序表

python 中顺序表存储的两种基本形式：

顺序表中存储的是大小固定的元素。顺序表中存储的是元素指向的地址。

顺序表的表现形式

一体式顺序表的表头存储的就是表头，存储表的大小分离式顺序表的表头存储的表头指向新的地址，地址指向表的大小等信息。

python中顺序表的扩充

属于加倍式，每次需要扩充是增加当前的4倍大小, 超过50000的阀值一倍一倍增加

顺序表的效率

python中顺序表操作的时间复杂度：

index[] O(1)index assignment O(1)append() O(1)pop() O(1)pop(i) O(n)insert(i, item) O(n)del O(n)iteration O(n)contains O(n)list[x:y] O(k)del list[x:y] O(n)reverse O(n)sort O(logn)multipy O(nk)