程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 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讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?

黄申 2019-01-18
你好,我是黄申。
作为程序员,你一定非常清楚复杂度分析对编码的重要性。计算机系统从最初的设计、开发到最终的部署,要经过很多的步骤,而影响系统性能的因素有很多。我把这些因素分为三大类:算法理论上的计算复杂度开发实现的方案硬件设备的规格
如果将整个系统的构建比作生产汽车,那么计算复杂度相当于在蓝图设计阶段,对整个汽车的性能进行评估。如果我们能够进行准确的复杂度分析,那么就能从理论上预估汽车的各项指标,避免生产出一辆既耗油又开得很慢的汽车。
可是,你也常常会发现,要准确地分析复杂度并不容易。这一讲,我来说说如何使用数学的思维,来进行系统性的复杂度分析。

基本概念

我先带你简短回顾一下几个重要概念,便于你稍后更好地理解本节的内容。
算法复杂度是一个比较抽象的概念,通常只是一个估计值,它用于衡量程序在运行时所需要的资源,用于比较不同算法的性能好坏。同一段代码处理不同的输入数据所消耗的资源也可能不同,所以分析复杂度时,需要考虑三种情况,最差情况、最好情况和平均情况。
复杂度分析会考虑性能的各个方面,不过我们最关注的是两个部分,时间和空间。时间因素是指程序执行的耗时多少,空间因素是程序占用内存或磁盘存储的多少。因此,我们把复杂度进一步细分为时间复杂度和空间复杂度。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(7)

  • Being
    老师,我想了很久,不能确定,双向BFS的停止条件跟maxDegrees有关,也就是说最坏的情况是刚好到maxDgrees时搜索到,所以时间复杂度应该是 maxDgrees * 2*(V+E),运用四则运算法则,这个队列循环了maxDgrees次,每一次对node的访问都是(V+E),而双向是两端并进所以乘2,再根据主次分明,将常量这些去掉,最后就是O(V)。
    空间复杂度也和maxDegrees有关,队列有两个maxDegrees*(V+E),visited的容器也有两个,同样的,主次分明来说,其他的变量就可以忽略了,然后用四则运算法则来计算,就是相加,最后是O(V)
    以上都是算的最坏情况,最好情况是O(1),平均情况? 最后跟最坏情况一样,是使用排列组合法则推导吗?我后面再试试。

    作者回复: 分析的很详细👍,这里E是指边的数量?V是指结点的数量?

    2019-01-19
    5
  • pyhhou
    思考题感觉要根据具体图的情况来看具体时间复杂是多少,就之前的六度关系的例子,假设把关系看作是一个树,每个结点都有 n 个子结点,要确认两个人是几度好友,也就是确认两个结点相距多少层,如果是单向广度优先搜索,时间复杂度 O(n^degree),双向可以运用加法法则,两边同时出发,时间复杂度 2 * O(n^(degree/2)),空间复杂度是队列中暂存的结点的最大值,和时间复杂度一样

    作者回复: 是的

    2019-03-16
    2
  • 炎发灼眼
    老师,有一点不明白,为什么在计算归并的复杂度时,切分的复杂度就是按照节点来算,是算每次切的时间么?而归并的时候是算指数的,合并的时候,其实也是两个节点合并一个,应该是按照合并的数目来算的。

    作者回复: 你这里的归并是指归并排序,对吧?归并排序的时间复杂度是O(n * logn),其中logn表示二叉树的高度,而n表示二叉树的每一层,你都要扫描一遍长度为n的数组

    2019-10-10
    1
  • 知行合一
    平均复杂度的计算稍微繁琐一些。如果距离为 n-1,只有 1 种可能,a 为数组中第一个字符,b 为数组中最后一个字符。如果距离为 n-2,那么 a 字符的位置有 2 种可能,b 在 a 位置确定的情况下只有 1 种可能,因此排列数是 2。以此类推,如果距离为 n-3,那么有 3 种可能,一直到距离 1,有 n-1 种可能。所以平均的扫描次数为 (1 *(n-1) + 2 *(n-2) + 3(n -3) + … + (n-1)1) / (1 + 2 + … + n),最后时间复杂度简化为 O(n)。
    老师,这个分母(1+2+•••+n)怎么理解

    作者回复: 表示扫描的总次数

    2019-12-11
  • Paul Shan
    算法的复杂度分析是一个统计+近似的过程,先用四则运算把所有消耗的成本统计出来,如果递归的话,可能用到画成递归树来求和,然后把一些低阶的复杂度全部删除只保留高阶的,多个变量需要表达成多变量的函数,最终得到一个最简表达式。
    2019-08-28
  • 天佑
    看不懂里面的数学符号,怎么来的,为什么是log...

    作者回复: 你所说的log是指二分查找或归并排序的时间复杂度log(n)对吧。这里的log是以2为底,如果8个数字,那么就要查找3次,或者划分3次,也就是log(8),以2为底

    2019-07-03
  • Being
    嗯,V是节点的数量,E是边的数量,根据邻接矩阵的概念来的。

    作者回复: 思路是对的,不过V和E我们通常可以使用平均连接数来进一步推导,便于比较不同算法的好坏。具体的我会在第17讲的例子中讲解。

    2019-01-20
收起评论
7
返回
顶部