TsingHuaDSA-绪论

该文章为清华大学数据结构与算法设计MOOC课程读书笔记.

1. Big O notation

1.1 O, Ω , Θ

big - o

当n足够大时,一定存在一个常识c,使得c·f(n)肯定能大于T(n),即能够成为它的上界

T(n)是用算法规模来表示的对应计算机基本操作的数量

同理得到下界

big - Ω

还有确界

big - Θ

1.2 对比

复杂度对比
Visual Compare

2. 算法分析

算法分析的两大内容就是:正确性 + 复杂度

你这个算法对不对?算出结果需要多少时间?多少空间?

2.1 级数

两大最重要的级数:算术级数 + 几何级数

  • 算术级数 O(n^2)


    算术级数

arithmetic progression is a sequence of numbers such that the difference between the consecutive terms is constant.

  • 几何级数 O(2^n)


    几何级数

geometric progression is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio.

  • 调和级数 O(logn)


    调和级数
  • 对数级数 O(nlogn)

对数级数
  • 幂方级数 O(n^k)


    幂方级数
  • 收敛级数 O(1)

收敛级数

2.2 循环

  • 算术级数 Arithmetic progression


    算术级数
  • 几何级数 Geometric progression

几何级数

2.3 封底估算 Back-Of-The-Envelope Calculation

A back-of-the-envelope calculation is a rough calculation. 一种非精确却又能抓住本质的估算。

算法 + 硬件

3. 迭代与递归

3.1 减治 Decrease and Conquer

将问题分解为:平凡问题 + 子问题

平凡问题:可以非常容易地得到解
子问题:结构上类似,只是规模小了的原问题

3.2 分治 Divide and Conquer

将问题分解为两个(或者多个)子问题

3.3 对递归的分析

  • 递归跟踪 Recursion Trace
    形象地列出每个递归实例,并根据每个递归实例的耗时来计算总耗时

  • 递归方程 Recurrence
    利用递归方程来推导出时间复杂度

一些结论

4. 动态规划

4.1 Memoization

利用一个table来存储计算结果,每计算一个递归实例时先查表看看是否已经计算过

4.2 Dynamic Programming

  • Fibonacci


    Fib的递归 VS 迭代动规
  • Longest Common Subsequence(LCS)

LCS理解
LCS递归

解:右下
计算的方向:右下到左上
重复计算:紫色的递归实例会被它下面的实例以及右边的实例调用,即被重复性地调用

LCS迭代动规

计算方向:左上到右下
无重复计算:每个计算单元由已计算好的左上或左或上的单元来求出。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 2017年3月26日,有点阳光,枣庄的天气还是那么干燥。这封信是写给三五年后的我自己,不知道那个时候的我看了这封信...
    苏演阅读 391评论 9 2
  • 今夜星星天边挂 夜深宁静窗前望 星星寄我相思苦 请明月代我问候 君心怨我伊人知 只恨你我相识晚 你心我早己读懂 伊...
    吉英子阅读 284评论 0 0
  • 827 我想去彼岸 所以我爱桥 踏实可信赖 如我的家人 桥能带我超越桥 我想去彼岸 所以我爱船 风浪中不离不弃 如...
    飞雪姐姐阅读 285评论 0 4