AI_第一部分 数据结构与算法（4.线性表之数组相关）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

从本篇开始我们就进入到具体的数据结构的学习之中了，你是否在面试的时候有面试官问过你，能解释一下数组的取值都是从下标0开始吗？能简单的说明一下线性表和顺序表表是个什么关系呢？......

第一、什么是线性表？和顺序表示什么关系呢？

线性表的定义:是指具有相同数据类型的n个数据元素的有限序列。n代表长度，n=0代表是一个空表。用L表示

顺序表的定义:线性表的顺序存储称为顺序表。其特点就是表中的逻辑顺序与物理顺序是相同的。

so,你说他两啥子关系，线性表是一种逻辑结构，顺序表是存储结构，是不同层面的。

第二、什么是数组？

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

第三、这些以及后续要介绍的链表之间是什么关系呢？

3.1线性表结构的数据类型有哪些呢？

数组、链表、队列、栈都属于线性表的范畴。

3.2.如何理解线性表定义中的相同数据类型？

有了连续的内存空间和相同的类型数据结构，让线性表有了一个重要的特性：随机访问，即通过首地址和元素的序号就可以在O(1)的时间内找到指定的元素。但是在进行删除和插入元素的操作时，为了保持连续性，就需要做大量的数据“搬迁”工作。

3.3这些数据结构是一个什么样的关系呢？

第四、数组下标问题的解释：

数组是如何随机的访问数组中的元素呢？

我们举一个例子：

int [] a = int[10] (int[]表示的是申明一个整数类型的数组，在强语言中必须要进行申明后才能使用 的，这个和弱语言类型是有区别的，希望大家注意)

计算机呢给数组a[10]分配了一块连续的内存空间1000~1020，其中首地址为base_address=1001.计算机会给每个内存单元分配一个地址，计算机是通过内存地址来访问内存中的数据，当计算机要随机的访问数组中的某个元素时，它会首先通过寻址公式，计算出当前元素存储的内存地址：a[i]_address = base_address + i * data_type_size,其中data_type_size表示数组中元素类型的大小的基本单位，什么意思呢？比如本文中用的int类型的数据，则data_type_size=4(字节)。

好了，现在我们就可以解释：数组的取值都是从下标0开始这个问题，从数组存储的模型来看，“下标”比较准确的定义应该是叫做“偏移”，若用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地址，a[k]也就是偏移为k个data_type_size的位置，所以：a[k]_address = base_address + k * data_type_size,其中data_type_size

若从1开始，则计算公式就会是：a[k]_address = base_address + (k-1) * data_type_size,其中data_type_size.从公式可以看出：若从1开始编号，每次随机访问数组元素都多了一次减法运算的操作，对于CPU来说，就是多了一次减法指令。

当然这个解释呢，只是从一个方面佐证了其从0开始的合理性，如果有兴趣的小伙伴可以去了解了解c语言的历史，我想你会获得意想不到的收获。（本人就喜欢看历史，哈哈）。

说明：学过或者写过c语言的同学应该知道，上文中比如你定义一个数组a 其实a 和a[0] 是在使用上等价的，所以才会有我上面的推论。

第五、线性表插入和删除效率问题讨论

在很多开发人员潜意识里，链表适合插入、删除操作，时间复杂度O(1),数组等线性表，适合查找，其查找时时间复杂度为O(1),这种认知是存在片面性的，数组是适合查找，查找的时间复杂度并不是O(1),即使是排好序的数组，你用二分查找，其时间复杂度也是O(logn),so，数组是支持随机访问的，根据下标随机访问的时间复杂度为O(1)。那其插入和删除操作的时间复杂度呢？是O(n)(平均的)，鉴于我们讲过如何计算时间复杂度O，这里我就不进行推到了，有兴趣的同学可以自己试试。那有人就问了，那谁的查找时间复杂度是O(1)呢？我先可以告诉大家，这个后续也会给大家提到的，就是hash存储。

好了，本期关于线性表的分享到此结束，从下一期开始我们看链表相关的内容，你有任何问题，请留言或者后台与我取得联系，在时间允许的情况下会及时回复你的问题，谢谢理解。

如果你觉得公众号的内容不错，可以推荐于身边的朋友，你的每次肯定和受益都会成为我前进的动力，一起加油！

注意：1.欢迎大家把自己的答案在最下面进行留言，或者后台留言。

2.此系列练习我会给出c语言的代码，当然现在的比较简单，目前还没有代码啦。