操作数组array的时间复杂度是什么?

操作数组array的时间复杂度是什么?

1 数组
数组是最最基本的数据结构,很多语言都内置支持数组。数组是使用一块连续的内存空间保存数据,保存的数据的个数在分配内存的时候就是确定的:

0_130261676331Xx
图 1.1 包含 n 个数据的数组
访问数组中第 n 个数据的时间花费是 O(1) 但是要在数组中查找一个指定的数据则是 O(N) 。当向数组中插入或者删除数据的时候,最好的情况是在数组的末尾进行操作,时间复杂度是 O(1) ,但是最坏情况是插入或者删除第一个数据,时间复杂度是 O(N) 。在数组的任意位置插入或者删除数据的时候,后面的数据全部需要移动,移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。

0_1302616849B2CF

图 1.2 向数组中插入数据

 

i. Almost all the operations are O(1) [i.e. omega times one]
ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.
Note! Hence, an array as a data structure is used where remove/insert operations are not required.

发表回复

您的电子邮箱地址不会被公开。