[数据结构与算法]算法与数据结构【30天】集训营——时间复杂度与空间复杂度（02）

数据结构与算法之间存在着本质联系，在某一类型数据结构上，总要涉及其上施加的运算，而只有通过对所定义运算的研究，才能清楚理解数据结构的定义和作用；在涉及运算时，总要联系到该算法处理的对象和结果的数据。在 “数据结构 ” 中，将遇到大量的算法问题，因为算法联系着数据在计算过程中的组织方式，为了描述实现某种操作，常常需要设计算法，因而算法是研究数据结构的重要途径。

以上是书本对算法的描述，简而言之：程序 = 重要 = 算法！

数据结构=逻辑结构+存储结构+操作

算法的定义及特性

五个重要的特点

定义：一系列有限的步骤

(1)有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
(2) 确定性。对千每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。
(3)== 可行性==。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
(4) 输入。一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
(5) 输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

注意：没有输出的算法是没有意义的！

评价算法优劣的基本标准

(1)正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
(2) 可读性。一个好的算法，首先应便千人们理解和相互交流 ， 其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且十分难调试和修改。
(3) 健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
(4) 高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。

时间复杂度和空间复杂度是衡量算法的两个主要指标。目前我们主要把重点放在时间复杂度上！

程序不等于算法！因为程序可以无穷的，但是算法是有穷的。

算法的时问复杂度

衡量算法效率的方法主要有两类：事后统计一法和事前分析估算法。

定义：算法中基本操作重复的执行的时间是问题的规模n的某个函数F(n)

问题规模和语句频度

也就是给定一段程序，你要有对该程序的时间复杂度能够有一个准确的分析和认识，能够从不同的程序代码中选择好的算法来实现我们的任务。

大O法

大O法是语句频度的一个近似值，比如$$F(n)=3n^3$$
那么时间复杂度用大O法表示就是：$$O(n^3)$$
一般情况下， 算法中基本语句重复执行的次数是问题规模$n$的某个函数$F_{(}n)$, 算法的时间量度,记作
$$T(n)=O(F{}_n)$$

我们观察下面的一个程序案例：

{x++;s=O;}//1
for(i=O;i<10000000;i++) {x++;s=0;}//2

我们猜想一下上面的时间复杂度是多少？可能第一个时间复杂度，很容易就判断出来了，执行一次的程序为1，利用大O法，故时间复杂度为$O(1)$，但是有的人可能对于第二个不是很明白了，为什么第二个的时间复杂度和第一个是一样的呢？

这里给出时间复杂度的具体计算方法：实际上，如果算法的执行时间不随问题规模n的增加而增长，算法中语句频度就是某个常数。即使这个常数再大， 算法的时间复杂度都是 O(1)。简而言之，就是它的执行次数不会随着n而变化，因为它的执行次数是有限的。

为了让大家可以更加清楚的了解此类知识在考试中的具体考法，这里引用几个例子：

常数阶案例：

线性阶案例：

平方阶案例：

立方阶案例：

对数阶案例：
两边同时取对数，log为底的对数，利用数学知识即可求解
常见函数增长率

时间复杂度知识点例题

在计算和考察时间复杂度的时候，对数的考察往往容易被忽略，下面给出一些考察例题：

答案：$$B$$
程序不一定满足有穷性， 如死循环、 操作系统等， 而算法必须有穷。 算法代表对问题求解步骤的描述， 而程序则是算法在计算机上的特定实现。 本题容易错误选择C， 它只是算法的必要条件， 不能成为算法的定义。

答案：$$C$$
时间复杂度为 $O（n^2）$，说明算法的时间复杂度$(Tn)$，满足$T（n）\le C{n}^2$（c为比例常数），即 $T（n）=O（n^2）$，时间复杂度$T（n）$是问题规模$n$的函数，其问题规模仍然是n，而不是$n^2$。

分析时间复杂度
答案：$$D$$
找出基本运算i=i*2,设执行次数为t,则$2^t<=n,即t<=lo{g}_{2}n$,因此时间复杂度$T(n)=O(lo{g}_{2}n)$。

！！注意！！！

答案：B，该算法考察了递归思想

上述就是时间复杂度常考的题型，涵盖了历年的考题与解析。

算法的复杂度取决于问题的规模和待处理数据的初态。

总结：对于算法分析时间复杂度，我们要明白其本质，比如需要限定的数字，直接为O(1)，其次遇到X=num*X，根据大O法：$O(lo{g}_{num}X)$，如果在其程序外还嵌套了其他的，对应的乘上去即可，最后就是遇到 $X^3$的形式，直接就是$X^{1/3}$。

空间复杂度

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、 常数、 变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数， 则称这个算法为原地工作，辅助空间为O(1),

空间=自己所占空间+输入输出所占空间+额外辅助空间

原地工作：若辅助空间相对于输入数据是常数

算法优化

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）根据定义，前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55

给定一个正整数n，求出斐波那契数列第n项（这时n较小）

解法一：最笨，效率最低，暴力递归

def f0(n):
    if n==1 or n==2:
        return 1
    return f(n-1)+f(n-2)

至少也还是用到了递归的思想，哈哈哈，但是这个时间复杂度非常高，不利于我们程序的高效执行，那么为什么会这样呢？我们可以看看递归的具体思想是什么：

比如想求f(10)，计算机里怎么运行的？
每次要计算的函数量都是指数型增长，时间复杂度$O(2^{（N/2）})<=T(N)<=O(2^N)$,效率很低。效率低的原因是，进行了大量重复计算，比如图中的f(8),f(7)…等等，你会发现f(8)其实早就算过了，但是你后来又要算一遍。

如果我们把计算的结果全都保存下来，按照一定的顺序推出n项，就可以提升效率， 斐波那契（所有的一维）的顺序已经很明显了，就是依次往下求。

def f1(n):
    if n==1 or n==2:
        return 1
    l=[0]*n
    l[0],l[1]=1,1
    for i in range(2,n):
        l[i]=l[i-1]+l[i-2]
    return l[-1]

时间复杂度o(n)，依次往下打表就行，空间o(n).

继续优化：既然只求第n项，而斐波那契又严格依赖前两项，那我们何必记录那么多值呢？记录前两项就行了

def f2(n):
    a,b=1,1
    for i in range(n-1):
        a,b=b,a+b
    return a

此次优化做到了时间o(n),空间o(1)

定一个由0-9组成的字符串，1可以转化成A，2可以转化成B。依此类推。。25可以转化成Y，26可以转化成z，给一个字符串，返回能转化的字母串的有几种？

比如：123，可以转化成

1 2 3变成ABC，

12 3变成LC，

1 23变成AW，三种，返回三，

99999，就一种：iiiii，返回一。

分析：求i位置及之前字符能转化多少种。

两种转化方法，一，字符i自己转换成自己对应的字母，二，和前面那个数组成两位数，然后转换成对应的字母

假设遍历到i位置，判断i-1位置和i位置组成的两位数是否大于26，大于就没有第二种方法，$f(i)=f(i?1)$,想反，等于$f(i?1)+f(i?2)$

注意：递归式不确定，不能用矩阵快速幂

如果你喜欢算法，你可以去牛客网上或者LeetCode上刷题，不同的问题有很多种解题思路，但是并不是每一种解题思路的效率都是一样的。

最详细】数据结构（C语言版 第2版）第一章课后习题答案 严蔚敏 等 编著

第 1 章绪论

1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结

构、抽象数据类型。

答案：
数据 ：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。 如数学计算中用到的整数和实数， 文本编辑所用到的字符串， 多媒体程序处理的图形、图像、声音、画等通过特殊编码定义后的数据。

数据元素 ：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项 ：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象 ：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是
集合 N={0 ，± 1，± 2，, } ，字母字符数据对象是集合 C={‘A’， ‘ B’，, ， ‘ Z’， ‘ a’，‘ b’，, ，‘ z’}，

学生基本信息表也可是一个数据对象。数据结构 ：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合， “结构”就是指数据元素之间存在的关系。

逻辑结构 ：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构： 数据对象在计算机中的存储表示，也称为 物理结构 。

抽象数据类型 ：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：

例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。 对于整个表来说， 只有一个开始结点 ( 它的前面无记录 ) 和一个终端结点 ( 它的后面无记录 ) ，其他的结点则各有一个也只有一个直接前趋和直接后继。

学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。

这些学生记录在计算机中的存储表示就是存储结构。 如果用连续的存储单元 ( 如用数组表示 ) 来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

答案：

（ 1）集合结构
数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。
（ 2）线性结构
数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。
（ 3）树结构
数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。
（ 4）图结构或网状结构
数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图形结构或网状结构。其中树结构和图结构都属于非线性结构。

图形在前面的文章有详细的展示

4．存储结构由哪两种基本的存储方法实现？

答案：

（ 1）顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

（ 2）链式存储结构
顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

5．选择题

（ 1）在数据结构中，从逻辑上可以把数据结构分成（ ）。
A．动态结构和静态结构 B ．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D ．内部结构和外部结构
答案： C

（ 2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。
A．存储结构 B ．存储实现
C．逻辑结构 D ．运算实现
答案： C

（ 3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。
A ．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
答案： B

（ 4）以下说法正确的是（ ）。
A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
答案： D
解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构
的各数据元素的集合。

（ 5）算法的时间复杂度取决于（ ）。
A．问题的规模
B．待处理数据的初态
C．计算机的配置
D． A 和 B
答案： D
解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些
排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏
以及平均时间复杂度的评价。

（ 6）以下数据结构中， （）是非线性数据结构
A．树 B ．字符串 C ．队列 D ．栈
答案： A

试分析下面各程序段的时间复杂度。

（1）

x=90; y=100; 
while(y>0) 
	if(x>100) 
		{x=x-10;y--;} 
else x++; 

答案： O(1)
解释：程序的执行次数为常数阶。

（ 2）

for (i=0; i<n; i++) 
	for (j=0; j<m; j++) 
		a[i][j]=0; 

答案： O(mn)
解释：语句 a[i][j]=0; 的执行次数为 mn。

（ 3）

s=0; 
for i=0; i<n; i++) 
	for(j=0; j<n; j++) 
		s+=B[i][j]; 
sum=s; 

答案： O(n 2)
解释：语句 s+=B[i][j]; 的执行次数为 n2。

（ 4）

i=1; 
while(i<=n) 
	 i=i*3; 

答案： O(log 3n)
解释：语句 i=i*3; 的执行次数为 log 3n 。

（ 5）

x=0; 
	for(i=1; i<n; i++) 
		for (j=1; j<=n-i; j++) 
			x++; 

答案： O(n 2)
解释：语句 x++; 的执行次数为 n-1+n-2+ …＋ 1= n(n-1)/2 。

（ 6）

x=n; //n>1 
y=0; 
while(x ≥ (y+1)* (y+1)) 
	y ++; 

答案： O( $n^{\frac{1}{2}}$ ) 解释：语句 y++;

每文一语

坚持就是胜利！