程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
22562 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?

黄申 2019-01-23

你好,我是黄申。

之前的 17 讲,我们从小处着眼,介绍了离散数学中最常用的一些知识点。我讲到了很多数据结构编程语句基础性算法。这些知识点看似是孤立的,但是内部其实有很多联系。今天这一节,我们就来总结一下前面讲过的内容,把之前讲过的内容串联起来。

数据结构

首先,我们来看一些基本的数据结构,你可别小看这些数据结构,它们其实就是一个个解决问题的“模型”有了这些模型,你就能把一个个具体的问题抽象化,然后再来解决。

我们从最简单的数据结构数组开始说。自从你开始接触计算机编程,数组一定是你经常使用的数据结构。它的特点你应该很清楚。数组可以通过下标,直接定位到所需的数据,因此数组特别适合快速地随机访问。它常常和循环语句相结合,来实现迭代法,例如二分查找、斐波那契数列等等。

另外,我们将要在“线性代数篇”介绍的矩阵,也可以使用多维数组来表示。不过,数组只对稠密的数列更有效。如果数列非常稀疏,那么很多数组的元素就是无效值,浪费了存储空间。此外,数组中元素的插入和删除也比较麻烦,需要进行数据的批量移动。

那么对于稀疏的数列而言,什么样的数据结构更有效呢?答案是链表。链表中的结点存储了数据,而链表结点之间的相连关系,在 C 和 C++ 语言中是通过指针来实现的,而在 Java 语言中是通过对象引用来实现的。

© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(9)

  • hua168
    老师,问3个很重要的题外问题:
    1. 大专学历,想直接自学考本科或研究生,自考学历中大型公司承认的吗?
    2. 大公司对年龄有限制的吗?
    3. 30多岁,运维,只有小公司工作经验,技术一般,发展方向是什么?
       很多IT公司好像都不要年龄大点的~~人生80,那不是40岁就没得工作了?

    作者回复: 我一个个来回答
    第一个,我个人对这方面不太清楚,不过我觉得关键看结果,如果你能考上大学,拿到合格的文凭,应该就没问题。具体你可以咨询一下大公司的人事。
    第二个,一般情况下没有特殊要求,关键看你牛不牛。
    第三个,这个很难给出一个具体的答案,要看你个人的兴趣和特长,如果能找到一个结合点就最好了。
    至于年龄问题,我觉得如果一个公司只看年龄,那就太片面了。从另一个方面来考虑,我们自己也要不断地充电,才不会被时代所淘汰。

    2019-01-23
    10
  • 草原上的奔跑
    本篇黄申老师讲了数学的思想在编程里的具体实践落地,讲的太好了。数据结构,编程语句,基础算法,这些都有数学的思想在里面。之前自己没有去联想它们,造成的结果就是数学的思想悬在空中,写代码是写代码,数学思想是数学思想,两者不沾边,偶尔两者会碰撞一下,就会觉的很开心。黄申老师在这里给我指明了方向,让数学思想实际内化到编程之中,编程背后的逻辑支撑,提供给了我们为什么这么做的理由。想起来一句话,知识点我都知道,但是,实际去做,去把知识点串联起来,融会贯通,我就不知道了!!!

    作者回复: 很高兴我的专栏能给你带来帮助!在后面的几大模块中,我会继续发挥这种风格

    2019-01-25
    3
  • Jerry银银
    很喜欢今天的文章。把编程中的细节和数学关联,让人茅塞顿开
    2019-01-23
    3
  • Boxing
    老师阶段性总结的非常棒。希望老师在后面课程讲得更接地气,通俗易懂,谢谢!

    作者回复: 我会继续加油💪

    2019-03-19
    2
  • alic
    干货
    2019-01-23
    1
  • Paul Shan
    数组是基于一块物理内存的数据结构,结构紧凑,可随机访问,是实现堆,栈,队列和完全二叉树,哈希表等数据结构的砖头,这些数据结构的特点是能够充分利用数组结构紧凑的特点,还可以享用随机访问的便利,对于扩展和删除虽然单步复杂度较高,但是对数组大小的选择是基于倍数为2的等比数列,可以一定程度均摊了复杂度。数组的缺点是所有元素都存储在一块连续的内存里,伸缩的时候就只能大块搬运效率不高,而且所有元素的序列是全局固定的(为了随机访问),要调整顺序,也只能全局处理,例如为了保证大小顺序,插入删除几乎需要对所有元素都要调整。
    链表的是基于逻辑关系的线性结构,元素之间的关系是通过指针联系的,关系较弱,相对于数组而言,这带来两个坏处,一个是增加了存储指针的成本,一个是没法像数组那样全局根据一个下标随机访问了。不过这中松散的节点关系也带来两个好处。一个是不再需要大块内存了,可以串起零散的存储区域,方便扩展。还有一个是插入删除非常方便,只要局部调整即可。链表的这种用指针串联元素的思想玩出的花样远远多于数组,是队列,栈,树,图等高级数据结构的基础。
    哈希表是数组和链表思想的扩张,希望通过元素而非下标来访问指定的对象,也充分体现了算法设计的均衡思想。假设CPU的速度是无限的,我们只需要链表来代替哈希表,对其线性查找即可。如果内存是无限的,我们只需要一个无穷大的数组,根据下标访问即可,可惜两者都不是无限的。我们就分配一块内存,然后建立元素到下标的hash映射,用hash表来平衡内存和CPU的使用。
    栈很多算法中作为解决问题的工具,例如括号匹配算法等。递归函数的作用域存在后进先出的特点,也会用到栈。队列更多的是分配资源的方法,以及某些和时间有效性有关的地方,这些地方都会用到队列先进先出的特点。
    条件语句是选择程序的分支,程序代码中会有很多分支,但是运行过程中只会根据条件选择一支。这就像决策的时候,潜在选项有不少,决策只能选一条。
    循环语句,是系统自相似的部分,每次循环都要离终止条件前进一步,最终结束循环,不然会死循环。
    函数递归和循环类似,反应了系统自相似的部分,但是比循环的边界更加清楚,基础情况定义的更加明确,每次状态变化都朝着基础情况演进。
    回溯算法是把状态组织成一棵树,深度或广度优先递归遍历这棵树。
    2019-08-29
  • 栾~龟虽寿!
    真的感谢老师,我感觉钱花的太值了。

    作者回复: 很高兴这门课程对你有帮助!

    2019-05-05
  • 木刻
    老师的造诣让人望尘莫及啊,我这辈子是不行了😂

    作者回复: 多多实践和总结,你也会有自己的独到的见解和心得 ☺️

    2019-03-24
  • 苦行僧
    数组 堆栈 队列 链表 二叉查找树 平常基本用这些
    2019-02-28
收起评论
9
返回
顶部