算法一撇之数据结构

算法一撇之数据结构

算法是的基础应该是数据结构,适合的数据结构能优雅的解决问题。

数组

数组的最大优点是可以快速查询。数组最好的应用在于索引有语意的情况。

动态数组

数组的空间是有限的,那么如果增加或者删除的时候,开辟空间的长度不够或者多余的时候,应该怎么办呢?

一个直接的方法是。相应的把内存空间扩张或者收缩相应的倍数,一般可以设置为两倍。

动态数组的话,因为开辟的空间,每一次都需要将原本的数据复制到新的array上来。所以这个操作的复杂度是O(n)。

但是从概率上来说,你执行了n次操作之后才会有一次扩容操作。操作均摊下来,时间复杂度应该是 O(1)

当......