专栏首页python编程军火库AI_第一部分 数据结构与算法(4.线性表之数组相关)

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语言的代码,当然现在的比较简单,目前还没有代码啦。

本文分享自微信公众号 - python编程军火库(PythonCoder1024),作者:还是牛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 08 | Tornado源码分析:IOLoop 之 事件循环

    各位朋友: 大家端午节安康,本期我们来聊聊 IOLoop 中最重要的一个方法----start(),为何这个方法如此之重要呢?写过 Tornado程序...

    还是牛6504957
  • 02 | Tornado源码全貌:上帝视角看Tornado

    正文共:1610 字 8 图 预计阅读时间:5 分钟 本篇主要从宏观的角度来为大家呈现 Tornado 源码的全貌,从上帝视角来感受一下源码的...

    还是牛6504957
  • 5分钟面试指南(第三篇 编码让我头大)

    本部分我们会为大家提供一些python初级工程师在面试过程中遇到的常见的面试题目,期望达到的效果:

    还是牛6504957
  • 尝鲜 ES2019 的新功能 [每日前端夜话0x38]

    ECMAScript 每年都会发布一个新版本,其中的提案是已经正式通过的,并分发给开发者和用户。本文将讨论该语言的最新版本,以及它又具有了什么新功能。

    疯狂的技术宅
  • Python第三十一课:Numpy数组操作

    接下来我们会学习如何改造数组方便我们使用,这里的改造包括对数组进行变形,翻转或者转置数组,连接数组,以及分割数组等等。

    HuangWeiAI
  • js中reduce的用法(二) 详解与注意事项

    reduce()是将数组数据的每个元素累积为一个值的最佳方法,所以本篇文章我们就来详细介绍一下JavaScript中reduce()的使用方法。

    用户6973020
  • 漫谈数仓五重奏

    从传统数仓到互联网数仓,有很多相似点也有很多不同点,互联网数仓的发展比较有代表性的就是阿里爸爸了,以下是《阿里大数据之路》中的数据体系架构图。

    王知无
  • python数据科学系列:numpy入门详细教程

    python数据科学基础库主要是三剑客:numpy,pandas以及matplotlib,每个库都集成了大量的方法接口,配合使用功能强大。平时虽然一直在用,也看...

    luanhz
  • 开发 | 为个人深度学习机器选择合适的配置

    AI科技评论按:对于那些一直想进行深度学习研究的同学来说,如何选择合适的配置一直是个比较纠结的问题,既要考虑到使用的场景,又要考虑到价格等各方面因素。 日前,m...

    AI科技评论
  • 深度学习中的数据简介 | PyTorch系列(十)

    欢迎回到这个关于神经网络编程的系列。在这篇文章中,我们将介绍Fashion-MNIST数据集。

    AI算法与图像处理

扫码关注云+社区

领取腾讯云代金券