下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 03 | 如何计算算法的复杂度
00:00 / 00:00
标清
  • 高清
  • 标清
  • 普清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程，可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18877
免费
01 | 合格程序员的第一步：算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解：数组&链表
06 | 面试题：反转一个单链表&...
07 | 理论讲解：堆栈&队列
08 | 面试题：判断括号字符串是...
09 | 面试题：用队列实现栈&用...
10 | 理论讲解：优先队列
11 | 面试题：返回数据流中的第...
12 | 面试题：返回滑动窗口中的...
13 | 理论讲解：哈希表
14 | 面试题：有效的字母异位词
15 | 面试题：两数之和
16 | 面试题：三数之和
17 | 理论讲解：树&二叉树&二...
18 | 面试题：验证二叉搜索树
19 | 面试题：二叉树&二叉搜索...
20 | 理论讲解：二叉树遍历
21 | 理论讲解：递归&分治
22 | 面试题：Pow(x,n)
23 | 面试题：求众数
24 | 理论讲解：贪心算法
25 | 面试题：买卖股票的最佳时...
26 | 理论讲解：广度优先搜索
27 | 理论讲解：深度优先搜索
28 | 面试题：二叉树层次遍历
29 | 面试题：二叉树的最大和最...
30 | 面试题：生成有效括号组合
31 | 理论讲解：剪枝
32 | 面试题：N皇后问题
33 | 面试题：数独问题
34 | 理论讲解：二分查找
35 | 面试题：实现一个求解平方...
36 | 理论讲解：字典树
37 | 面试题：实现一个字典树
38 | 面试题：二维网格中的单词...
39 | 理论讲解：位运算
40 | 面试题：统计位1的个数
41 | 面试题：2的幂次方问题&...
42 | 面试题：N皇后问题的另一...
43 | 理论理解：动态规划（上）
44 | 理论理解：动态规划（下）
45 | 面试题：爬楼梯
46 | 面试题：三角形的最小路径...
47 | 面试题：乘积最大子序列
48 | 面试题：股票买卖系列
49 | 面试题：最长上升子序列
50 | 面试题：零钱兑换
51 | 面试题：编辑距离
52 | 理论讲解：并查集
53 | 面试题：岛屿的个数&朋友...
54 | 面试题：岛屿的个数&朋友...
55 | 理论讲解： LRU Cache
56 | 面试题：设计和实现一个LR...
57 | 理论讲解：布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点：斐波拉契数列
61 | 白板实战番外篇：斐波拉契...
62 | 最后的一些经验分享
本节摘要

课件获取

关注“极客时间”微信公众号，在后台回复“算法试看”，即可获取试看课程的 PDF 课件。

本节重点

展开
 写留言

精选留言(29)

  • 妖艳货
    2018-10-11
    第一次买课，工作了，能够静下心来好好学习的机会是真的少

    作者回复: 嗯嗯，加油。

    18
  • 月之轮回2009
    2018-10-11
    老师我有个疑问，就是在代码中包含语言内置 API 时如何评估时间复杂度？例如在 O(n) 的循环里我加了一句 foo() 的函数调用，是应该把此函数调用的时间复杂度算进来还是应该视其为基本操作？

    作者回复: 看 foo 的具体实现。如果 foo 的操作是 o(1) 的，则整体还是 o(n)。如果 foo 本身就是 o(n)，那最后就是 o(n^2)

    8
  • Aliliin
    2018-10-11
    努力学习中，一次不懂就再一次。
    7
  • DY
    2018-10-11
    努力中...

    作者回复: 加油↖(^ω^)↗

    6
  • 土豆骗子
    2018-12-19
    老师，o(logN)这个，为什么不写底数啊

    作者回复: O都是估算复杂度的数量级，所以没底也差不多。

    5
  • John
    2018-10-30
    请问下，视频最后一个例子化为主定理是不是 T(n) = 2T(n) +1; 所以算出来T(n)=n^2 呢。

    作者回复: https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86 ： 主定理要求 T(n) = aT(n/b) + f(n) 中的 b>1，所以这里不能用主定理。直接从递推公式分析： F(n) = F(n-1) + F(n-2) 每次都是两倍的计算，不断展开。

    4
  • CGL
    2018-10-16
    老师，为啥说递归的时间复杂度是2的n次方呢？ 就如您所举例子，n为6的时候是20多次计算，n^2也才36,2^n都已经64了。那复杂度不是最接近O(n2)么。

    作者回复: 是指数级的复杂度，但是并不代表就是正好等于 2^n，时间复杂度本来就是数量级上的粗略估计。

    针对你上面的例子：6的时候的确如你所说没有 n^2 大，但是如果10或者20的时候，整体复杂度肯定高于 n^2

    3
  • 叶子
    2018-10-15
    O(k^n)那里应该是O(2^n)啊？！
    3
  • Alexdown
    2018-10-12
    O(n^3) N Cube complexity

    作者回复: 👍🏻👍🏻

    3
  • 张青天
    2019-01-26
    你好，O(log n)这个应该是 i = i^2 吧？
    1
    2
  • Big O 是指时间复杂度，还是空间复杂度，除了这两种衡量标注，还有别的计算复杂度的标准吗？
    1
  • 时间复杂度就等同于当前计算的次数吗？时间复杂度是运算完成所需的总时间吗？
    1
  • 老师，是否可以提供大量的计算复杂度的题目
    1
  • 杜鹏
    2019-01-13
    searching in sorted matrix seems like T(n) = 2 * T(n/2) + O(1) which turns out to be O(n) time complexity
    1
  • 信仰年轻
    2018-12-01
    O(k^n) 难道不是O(2^n)吗
    1
  • Wen
    2018-10-19
    斐波那契数列的这个函数时间复杂度是多少？
    1
  • Wilson
    2018-10-11
    小白问：3层for循环时间复杂度是n的3次方？

    作者回复: 对的。假设你的循环体每层都是 N 的循环，且没有一些特殊的循环终止条件。

    1
  • 7190zxh
    2018-10-11
    这个学习方式我喜欢，期待老师的课程😁
    1
  • 学习中希望后面的课程能作用于项目
    1
  • a旁观者
    2019-10-24
    老师您好，我是一名java开发从业者，工作5年左右，想转算法，听了您的几节课觉着还挺不错的，想问一下，这个视频课专栏，跟算法训练营这个重复吗？是否还有必要上训练营

    作者回复: 算法训练营是加强版，且有课程跟进、圈子、班主任和助教，所以更加能帮助你提高和坚持练习。

    1
去订阅《算法面试通关40讲》