有关数组操作的时间复杂度_数组查找的时间复杂度

数组的几种基本操作有：

1、读取元素

数组中是通过索引来读取元素的。对于数组，计算机会在内存中为其申请一段连续的空间，并且记录下索引为“0”的内存地址。若要访问一个元素，计算机会在索引为“0”的内存地址的基础上加上索引值。

例如   索引“0”的内存地址为 2000，若要查找索引值为8处的元素，则只需进行 2000+8=2008，便查找到了目标元素。

综上，只要知道内存地址就可以立即访问该元素，故时间复杂度为O(1)

 2、查找元素

在一个数组中进行元素的查找，最坏的情况就是目标元素是数组中的最后一个元素，或者目标元素不在该数组中。假设数组中有n个元素，这两种情况下我们都要对数组进行n此查找。

综上，根据最坏的情况，时间复杂度为O(n)

3、删除元素

分析时间复杂度，我们只需要分析在数组元素的删除操作中的最坏的情况来得出时间复杂度。

很容易想到，删除数组元素，最坏的情况是删除数组中的第一个元素。                                            删除数组中的第一个元素为一步，将剩下的(n-1)个元素依次向前移动一位。                                    则一共要进行1+(n-1)=n步操作。

综上，根据最坏的情况，时间复杂度为O(n)

4、插入元素

插入元素的事件复杂度的计算方法可以根据上一条删除元素的时间复杂度的计算方法来进行计算。

注：我们这里所计算的时间复杂度都是根据最基本的遍历算法来得出的。