day03 数据结构之 数组

1、什么是数组？

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同数据类型的数据。

• 线性表结构除数组外、栈、队列、链表也是线性表结构。非线性表有 堆、树、图等，在非线性表中数据之间不是简单的前后关系。

• 连续的内存空间和相同的数据类型：好处是随机访问。但是坏处是插入和删除需要搬移数据显得十分低效。

2、数组的查找时间复杂度。

img

数据适合查找操作：排序好的数组二分法查找时间复杂度为O（logn）; 数据支持随机访问，根据下标随机访问的时间复杂度为O（1）

3、低效的插入和删除

1. 插入

   • 数组的末尾插入 O（1）

   • 数组的开头插入 O（n）

   • 平均情况复杂度为： (1 + 2 + .....n) /n = O(n) 按照末尾向前插入的复杂度累计

   • 如果数据无序，我们插入数据x时，可以将指定位置m的数据搬移到数组末尾，将数据x插入到位置m 此时的时间复杂度为O（1）

img

2. 删除操作

   • 删除末尾元素： O（1）

   • 删除开头元素： O（n）

   • 平均情况复杂度： O（n）

   • 处理思路：当多个连续数据（a、b、c）需要删除时，先记录数据已经被删除，当数组内没有空间可以存储时，在触发一次真正的数据删除工作。大大减少了数据删除导致的搬移的工作

image

也是JVM的垃圾回收机制算法的核心思想。