数组是一个固定长度的存储相同数据类型的数据结构,数组中的元素被存储在一段连续的内存空间中。值得注意的是,Python中的列表,并不是严格的数组结构,因为列表的元素类型可以不同。列表中存储的其实是元素的索引地址,所以列表又具有数组的性质。

数组各种操作的复杂度

访问:数组可以使用索引访问,因此访问数组元素的时间复杂度为O(1),因为是连续存储;只需要知道数组的起始位置,和索引值就可以推算元素的实际地址。

查找:查找给定值,需要遍历每个元素,直到找到给定值为止,所以时间复杂度为O(n);

插入:在两个元素之间插入新元素,需要将插入之后的所有元素向后移动,所以时间复杂度为O(n);

删除:删除某个元素后,其后面的元素都要向前挪动一位,所以时间复杂度为O(n);

空间复杂度:O(n)

优缺点

1、可以通过索引取值,可以随机访问元素

2、声明时需要指定长度,可能会有造成空间浪费

3、插入和删除元素要重排元素,代价高

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/282