数组

数组

线性表存储结构，使用一块连续的内存空间，存储相同类型的一组数据

查找

数组支持按照下标随机访问数组元素，访问的时间复杂度为O(1)

删除

删除操作分析：

• 如果删除最后一个元素，只需要执行一次删除操作，时间复杂度为O(1)

• 如果删除第一个元素，除了执行一次删除操作，还需要执行n-1次数据搬移操作，时间复杂度为O(n)

删除操作的时间复杂度分析：

• 最好情况时间复杂度O(1)

• 最坏情况时间复杂度O(n)

• 平均情况时间复杂度O(n)

删除操作的优化：

• 如果不要求元素保持原有顺序，可以将需要删除元素，与最后一个元素做交换，然后删除最后一个元素，此时时间复杂度为O(1)

• 如果要求元素保持原有顺序，可以将多次删除操作集中在一起

添加

添加操作分析：

• 如果在数组末尾添加数据，只需执行一次添加操作，时间复杂度为 O(1)

• 如果在数组开始添加数据，需要执行n-1次数据搬移操作和一次添加操作，时间复杂度为O(n)

时间复杂度分析：

• 最好情况时间负载度：O(1)

• 最坏情况时间复杂度：O(n)

• 平均情况时间复杂度：O(n)

优化方法：

• 如果数组元素不需要保持原有顺序不变，可以在数组末尾添加元素，然后将最后一个元素与指定下标元素交换顺序