第一章绪论

本系列读书笔记参考自数据结构与算法经典问题解析第二版内容，习题答案部分有误，已勘正，部分严格证明参考算法导论第三版，水平有限，如有纰漏，尽请指出

基础概念

数据结构是计算机存储和组织数据的一种特定方式，通过特定的数据结构可以使相应的数据处理更加有效，常见的数据结构包括：数组，文件，链表，栈，队列，树，图等。

根据其元素组织方式，数据结构可分为两种类型：

线性数据结构：可以按线性次序访问元素，但它并不强制将所有元素连续存储在一起（如链表）。主要有链表，栈和队列
非线性数据结构：这种数据结构的元素是以非线性次序来存储和访问元素的，例如树和图

为了简化求解问题的过程，我们将数据结构和相关运算组合起来，统称为抽象数据类型ADT，其包含两个部分：数据的声明和运算的声明
常用的ADT包括：链表，栈，队列，优先队列，二叉树，字典，并查集，散列表，图等其他类型

当定义ADT时，不需要考虑其实现细节，仅当需要使用它们时，才考虑具体的实现。不同的ADT类型适用于不同的场合，需要我们灵活应用

算法分析的目标在于根据运行时间及其它的一些因素（如内存，开发者的工作量等）来比较算法的优劣
运行时间分析是指当问题的输入规模增大时，研究问题的处理时间是如何增加的

为了比较算法，以下是几种客观评价指标：

执行时间：不同的计算机会呈现出较大差异，不是一个好的评价标准
执行的语句数：因为执行的语句和编程语言以及程序员个人的编程风格相关，也不是一个好的评价标准
函数表示：假设用一个函数 $f(n)$ 表示一个算法的运行时间，而问题的输入规模用 $n$ 表示，通过比较不同算法对应的的 $f(n)$ ，就足以比较出各种算法的优劣

增长率是指随着输入规模的增加，算法运行时间增加的速度，也就是说对于一个给定的函数，我们会忽略相对影响更小的低阶因变量（当n很大时），例如对于下式我们可以认为：
$n^4+2n^2+100n+500\approx n^4$

image.png

算法分析

算法分析有如下三种类型：

最坏情况：定义算法最长运行时间的输入，这种输入使得算法运行最慢
最好情况：定义算法最短运行时间的输入，这种输入使得算法运行最快
平均情况：提供算法运行时间的预测值，此时假设输入是随机的，也就是说有：
$下界\leq 平均时间\leq 上界$

在我们定义了输入的不同类型后，我们需要对算法运行时间的上下界和平均时间做一个准确的定义

大O表示法

大O表示法给出了函数 $f(n)$ 的严格上界，我们记作 $f(n)=O(g(n))$ ，表示当输入规模 $n$ 很大时， $f(n)$ 的渐进上界是 $g(n)$

用更准确的数学语言来说，大O表示法定义为：
$O(g(n))=\{f(n):存在正常数c和n_0，使得对任意n\geq n_0,0\leq f(n)\leq cg(n)成立\}$

注意当边界只能大于（小于）而不能等于时，认为边界是渐进的但不是紧确的，也就是满足下式
$o(g(n))=\{f(n):存在正常数c和n_0，使得对任意n\geq n_0,0\leq f(n)< cg(n)成立\}$
此时我们称 $g(n)$ 是 $f(n)$ 的一个渐进非紧确上界

显然 $O(g(n))$ 是指所有与 $g(n)$ 具有相同增长率或比起增长率小的函数的集合，例如下图

image.png

但使用小o表示法，则不包含例如内的函数

$\Omega$ 表示法

与大O表示法类似， $\Omega$ 表示法给出 $f(n)$ 的严格下界，记作 $f(n)=\Omega (g(n))$ ，表示输入规模 $n$ 很大时， $f(n)$ 的渐进下界是 $g(n)$

用更准确的数学语言来说， $\Omega$ 表示法定义为：
$\Omega(g(n))=\{f(n):存在正常数c和n_0，使得对任意n\geq n_0,0\leq cg(n)\leq f(n)成立\}$

在使用中，我们需要尽可能求出满足条件的最大阶的 $g(n)$

同样的当满足下式
$\omega(g(n))=\{f(n):存在正常数c和n_0，使得对任意n\geq n_0,0\leq cg(n)< f(n)成立\}$

此时我们称 $g(n)$ 是 $f(n)$ 的一个渐进非紧确下界

例如 $f(n)=n^2+2n$ ，则 $f(n)=\omega(n)，f(n)=\Omega(n)$ 是正确的，而 $f(n)=\Omega(n^2)$ 也是正确的， $f(n)=\omega(n^2)$ 是错误的

$\Theta$ 表示法

$\Theta$ 表示法决定了算法的时间增长率上界和下界是否相同，如果大O表示法与 $\Omega$ 表示法给出的结果是一样的，那么 $\Theta$ 表示法也会给出相同的结果。而对于一个给定的函数，如果它增长率的上界和下界是不同的，那么 $\Theta$ 表示法需要通过分析所有可能的时间复杂度，然后得出平均情况下的结论（例如快速排序的平均情况，参见第十章）

$\Theta$ 表示法的数学含义：

对于函数 $f(n),g(n)$ ，如果存在常数 $c(c>0)$ 使得 $\lim_{n\to \infty}\frac{f(n)}{g(n)}=c$ ，那么有 $f(n)=\Theta (g(n))$
$\Theta(g(n))=\{f(n):存在正常数c_1,c_2和n_0，使得对任意n\geq n_0,0\leq c_1g(n)\leq f(n)\leq c_2g(n) 成立\}$

用图示表示以上表示法如下：

image.png

小结：

image.png

一些通用的计算规则：

image.png

渐进表示法的基本性质：

image.png

一些常用的数学公式：

image.png

分治法定理

分治法是指把一个问题划分为多个子问题，每个子问题是原问题的一部分，然后执行一些额外的工作来计算最后的答案，例如归并排序中，将原问题分为两个子问题，每个子问题都是原问题规模的一半，然后用 $O(n)$ 的额外工作完成归并，可以用下式表示
$T(n)=2T(\frac{n}{2})+O(n)$

我们把这种分治法思想推广，如果一个问题可以通过以下递归形式表示
$T(n)=aT(\frac{n}{b})+\Theta(n^k\log^pn),a\geq 1,b>1,k\geq 0$
则有如下几种情况：

当 $a>b^k$ 时， $T(n)=\Theta(n^{\log_b^a})$
当 $a=b^k$ 时
a. 如果 $p>-1$ ， $T(n)=\Theta(n^{\log_b^a}\log^{p+1}n)$
b. 如果 $p=-1$ ， $T(n)=\Theta(n^{\log_b^a}\log\log n)$
c. 如果 $p<-1$ ， $T(n)=\Theta(n^{\log_b^a})$
如果 $a<b^k$
a. 如果 $p\geq 0$ ， $T(n)=\Theta(n^{k}\log^{p}n)$
b. 如果 $p<0$ ， $T(n)=\Theta(n^k)$

这就是分治法的主定理，下面是一些使用主定理的例子

image.png

在主定理之上，还有一些变形：

变形1：当对于常数 $c,a>0,b>0,k\geq 0$ 和 $f(n),T(n)$ 有
$T(n)=\begin{cases}c&&n\leq 1\\ aT(n-b)+f(n)&&n>1 \end{cases}$
如果 $f(n)$ 的时间复杂度是 $O(n^k)$ ，则
$T(n)=\begin{cases}O(n^k)&&a<1\\ O(n^{k+1})&&a=1\\ O(n^{k}a^{\frac{n}{b}})&&a>1 \end{cases}$

变形2： $T(n)=T(\alpha n)+T((1-\alpha)n)+\beta n,0<\alpha <1,\beta>0$ ，则其复杂度为 $O(n\log n)$

猜测的方法

image.png

平摊分析

image.png

下面是一些典型习题及其解答

image.png

上图中F(2)还需要分为F(1)和F(0)，树有N层

image.png

解答有误，应该是假设是一颗满二叉树，则叶子节点少于 $2^n$ (事实上，依然属于 $2^n$ 阶)

时间复杂度： $O(2^n)$
空间复杂度： $O(n)$

image.png

也就是说 $T(n)=n+\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n}=\sum_{i=1}^{n}\frac{n}{i}=n\sum_{i=1}^{n}\frac{1}{i}=n\log n$

image.png

上式中注意省略掉这一步

image.png

最后编辑于：2019.09.29 14:23:31

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,271评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,275评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,151评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,550评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,553评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,559评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,924评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,580评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,826评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,578评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,661评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,363评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,940评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,926评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,156评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,872评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,391评论 2赞 342

第一章 绪论

基础概念

算法分析

分治法定理

推荐阅读更多精彩内容

第一章绪论