网易 | 数据结构和算法 | 学习笔记01：绪论

# 视频课程1：网易：数据结构和算法（讲师：小甲鱼）

# 视频课程2：数据结构（浙江大学： 陈越、何钦铭）

# 其中，【视频课程1】从课时1看到了课时3。讲师与课程无关的话有些多、会爆粗口、讲的一些段子也比较...，信噪比太低，不太适合于想专心学习的人。

# 于是换到了【视频课程2】，浙大的这个是比较中规中矩的课程，老师口齿清晰，PPT也可以在页面上下载。

┏━━━━━━━目录━━━━━━━┓

【视频课程1】

课时1数据结构和算法绪论

课时2谈谈算法20:12

课时3时间复杂度和空间复杂度1

【视频课程2】

1.1 什么是数据结构
1.2 什么是算法
1.3 应用实例：最大子列和问题

┗━━━━━━━━━━━━━━━━┛

——————————————————————【视频课程1】——————————————————————

【课时1】数据结构和算法绪论
程序设计=数据结构+算法

 

1、数据结构：

（1）数据元素相互之间存在的一种或多种特定关系的集合

（2）分为逻辑解构、物理结构

逻辑结构：数据对象中数据元素之间的相互关系

物理结构：数据的逻辑结构在计算机中的存储形式

 

2、逻辑结构

集合结构：除了同属一个集合，没有别的关系

线性结构：一对一

树形结构：一对多，层次关系，金字塔关系

图形结构：多对多

 

3、数据结构的存储形式：顺序存储、链式存储

顺序存储：地址连续的存储单元，数据间的逻辑关系和物理关系一致。如，数组

链式存储：存储单元可以是连续的也可以是不连续的，数据存储关系不能反映其逻辑关系，需要指针存放地址。

 

【课时2】算法

算法的特性

（1）      有零个或多个输入

（2）      有一个或多个输出，打印或返回

（3）      有穷性。循环次数有限，时间有限。

（4）      确定性。

（5）      可行性

算法的要求

（1）      正确性

（2）      可读性

（3）      健壮性

（4）      时间效率高、存储量低

 

 

【课时3】时间复杂度和空间复杂度（1）

1、  算法效率的度量方法

（1）      事后统计方法。

（2）      事前分析估算方法

2、耗时因素：

（1） 算法采用的策略、方案

（2）编译产生的代码质量

（3）问题输入的规模

（4）机器执行指令的速度

 * 在分析一个算法的运行时间是时，重要的是把基本操作的数量和输入模式关联起来。

* 函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的渐近增长快于g(n)。

* 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项）的阶数。

 

【这个课程废话太多了，不太好，学到此换浙江大学的视频】

———————————————————————【补充】———————————————————————

【先把时间复杂度和空间复杂度的定义补充完】

（1）空间复杂度：运行完一个程序所需内存的大小。

（2）时间复杂度：执行算法所需要的计算工作量。

* 算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

——————————————————————【视频课程2】——————————————————————

第一讲：基本概念

1.1 什么是数据结构

1、数据结构：数据对象在计算机中的组织方式
（1）逻辑结构
（2）物理存储结构
2、数据对象必定与一系列加在其上的操作相关联
3、 算法：完成这些操作所用的方法就是算法

4、解决问题方法的效率：

（1）跟数据的组织方式有关

（2）跟空间的利用效率有关

（3）跟算法的巧妙程度有关

5、递归算法更消耗内存。递归是程序调用自身，程序运行时代码和数据存到内存中，即要分配内存空间，递归程序每调用一次自身，操作系统都要为其分配相应的内存资源。

* 由于非递归函数的执行效率高，可将“尾递归”函数改为迭代函数（尾递归：return 自身）

 6、写程序计算给定多项式在给定点x处的值。

算法1：f(x)=a0+a1x+a2x^2+a3x^3+...+anx^n

(1+2+……+n)=(n2+n)/2次乘法——时间复杂度 T(n) = Cn^2+Dn （最高次项是平方项）

算法2：f(x)=a0+x(a1+x(a2+x(a3+x(...x(an-1+x(an)  ...))))

n次乘法——时间复杂度T(n) = Cn

* 测试程序运行时间：可以让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可。

7、抽象数据类型（Abstract Data Type）

（1） 数据类型

a.数据对象集
b.数据集合相关联的操作集

（2）抽象：描述数据类型的方法不依赖于具体实现
a. 与存放数据的机器无关
b. 与数据存储的物理结构无关
c. 与实现操作的算法和编程语言均无关

* 只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

1.2 什么是算法（Algorithm）

1、算法（定义）
（1）一个有限指令集
（2）接受一些输入（有些情况下不需要输入）
（3）产生输出
（4）一定在有限步骤之后终止
（5）每一条指令必须   ①有充分明确的目标，不可以有歧义  ②计算机能处理的范围之 ③描述应不依赖于任何一种计算机语言以及具体的实现手段

2、什么是好的算法

（1）空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
（2）时间复杂度T(n) —— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

*在分析一般算法的效率时，我们经常关注下面两种复杂度
（1）最坏情况复杂度Tworst( n )
（2）平均复杂度Tavg( n )

Tavg( n ) ≤ Tworst( n )

3、复杂度的渐进表示法

（1）T(n) = O(f(n)) 表示存在常数C >0, n0>0 使得当n≥n0 时有T(n) ≤ C·f(n) （最小上界）
（2）T(n) = Ω(g(n)) 表示存在常数C >0, n0>0 使得当n≥n0 时有T(n) ≥ C·g(n)（最大下界）
（3）T(n) = Θ(h(n)) 表示同时有T(n) = O(h(n)) 和T(n) = Ω(h(n)) （上界=下界，等价）

* 复杂度分析

 若两段算法分别有复杂度T1(n) = O(f1(n)) 和T2(n) =O(f2(n))，则
（1）T1(n) + T2(n) = max( O(f1(n)), O(f2(n)) )
（2）T1(n) * T2(n) = O( f1(n) * f2(n) )

结论：

（1）若T(n)是关于n的k阶多项式，那么T(n)=Θ(nk)

（2）一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

（3）if-else 结构的复杂度取决于if的条件判断复杂度
和两个分枝部分的复杂度，总体复杂度取三者中最大

* 一般遇到时间复杂度为T(N)=O(N^2)，都会想办法改为T(N)=O(NlogN)，大大提高效率

1.3 应用实例：最大子列和问题

算法1：求所有子序列的和，取最大值——3重for循环T(N)=O(N^3)

算法2：求所有子序列的和，取最大值——2重for循环T(N)=O(N^2)   # 对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可

算法3：（分治算法）分而治之：把序列一分为二，左右两边分别递归的找出左边的最大子列和、右边的最大子列和；还有一种情况是：跨越边界的子列和。最后的结果一定是这三个结果中的最大的一个。——T(N)=O(NlogN)

算法4：在线处理（线性算法）——T(N)=O(N)

* 读取每个值，如果当前子列和为负，则不可能使后面的部分和增大，抛弃之。

* “在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。