数据结构与算法1：数组操作的时间复杂度_数组的时间复杂度

数组为何从0开始计数

这几年学了VB、C、C++、C#、JAVA等编程语言，发现数组都是从零开始计数，从1开始不应该是
人类的惯性思维吗？直到今天接触了数据结构所给出答案才知道。

数组的概念：

• 线性表
• 连续的内存空间和相同类型的数据
  因为数组具有以上两个特性，计算机会给每个内存单元分配一个地址，通过地址来访问内存（数组）中的数据，当计算机随机访问某个数组元素时，会通过一个寻址公式来进行查找：

a[i]_address = base_address + i * data_type_size
1

解答：

• 从数组存储的内存模型来看，“下标”最确切的定义应该是“偏移（offest）”。如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就
  表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要用这个公式：

a[k]_address = base_address + k * type_size
1

如果数组从1开始计数，那么就变成了：

a[k]_address = base_address + (k-1) * type_size
1

此时对cpu来说，每次会多一次减法指令，造成不必要的运算浪费，所以数组从0开始计数

数组操作时间复杂度

在大二学习数据结构这门课的时候，时间复杂度对我来说一直是个陌生又抵触的词汇，但时至今日毕业一年，发现不论工作面试还是考研，这都是必考的内容，所以需要重新拾起来，学习理解以及运用。

• 查找
  数组相对于链表等其他结构，是比较适合查找操作的，但是查找时间复杂度并不为O(1)。即便是排序好的数组，用二分查找，时间复杂度也为O(log2n)。所以正确的表述应该是数组支持随机访问，根据下标随机访问的时间复杂度为O(1)
• 插入和删除
  插入和删除操作对于数组来说比较低效，假设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第K个位置。为了把第k个位置腾出来，我们需要将第k~n的数据往后挪，那么来分析一下其时间复杂度：
  如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。但如果
  在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是
  O(n)。因为在每个位置插入数据的概率是一样的所以时间复杂度平均为O(n/2)，省略常数1/2，即O(n)。
  删除同理。

数组插入与删除的应用：

• 插入
  如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法
  搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个
  存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模
  的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最
  后，把新的元素直接放入第 k 个位置。
  为了更好地理解，我们举一个例子。假设数组 a[10] 中存储了如下 5 个元素：a，b，c，
  d，e。
  我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5]，将 a[2] 赋值为 x
  即可。最后，数组中的元素如下： a，b，x，d，e，c。
  
  利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为
  O(1)。这个处理思想在快排中也会用到。
• 删除
  跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数
  据，不然中间就会出现空洞，内存就不连续了。
  和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的
  数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)。
  实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次
  删除操作集中在一起执行，删除的效率是不是会提高很多呢？
  我们继续来看例子。数组 a[10] 中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我
  们要依次删除 a，b，c 三个元素。
  
  为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。
  每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存
  储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬
  移。
  如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想吗？没错，
  数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个数据结构或者算
  法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。如果你细心留意，不
  管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子。