无序数组

需要考虑是否固定长度和下标位置,如果固定长度,且通过下标指定位置直接操作元素,那么时间复杂度就是O(1),如果不固定,那么就是O(N)。如下:

插入数据

  • 空间足够:直接添加在后面,时间复杂度为 O(1)
  • 空间不足:整个数组移到另一个空间,再添加元素,时间复杂度为 O(1)+O(N)=O(N)
  • 总的时间复杂度:O(1)+O(N)=O(N)

查找数据

使用顺序查找找到数据,时间复杂度:O(N)

修改数据

顺序查找到数据后,进行修改。时间复杂度为 O(N)

删除数据

使用顺序查找找到删除位置,再把删除位置后的所有元素前移一位,总时间复杂度:O(N)+O(N)=O(N)

有序数组

插入数据

查找插入位置用二分查找是 O(logN)。但是数组的插入操作为了保证有序性需要将插入位置后的元素全部后移一位, 这需要O(N)。所以总的时间复杂度是O(N)O(logN)+O(N)=O(N)

查找数据

二分法查找数据,时间复杂度为 O(logN)

修改数据

二分查找到数据后,进行修改。时间复杂度为 O(logN)。但因为是有序数组,还要进行排序。因为有序数组大部分都是有序, 即使使用冒泡排序时间开销也不会太大,所以此处我们使用冒泡序。冒泡排序时间复杂度为O(n²)。 总的时间复杂度:O(n²)+O(logN)。 小声BB:直接顺序比较不就行了吗?时间复杂度应该是O(N)

删除数据

使用二分查找找到删除位置,再把删除位置后的所有元素前移一位。总时间复杂度:O(logN)+O(N)=O(N)

参考资料