数据结构学习笔记（一）——基本概念

本贴参考学习内容为——中国大学MOOC浙江大学国家精品课《数据结构》，网址：https://www.icourse163.org/learn/ZJU-93001?tid=1468077441#/learn/announce

一、基本概念

1.1 什么是数据结构

$\cdot$ 数据对象在计算机中的组织方式

-逻辑结构
-物理存储结构

$\cdot$ 数据对象必定与一系列加在其上的操作相关联

$\cdot$ 完成这些操作所用的方法就是算法

1.2 抽象数据类型（Abstract Data Type）

$\cdot$ 数据类型

-数据对象集
-数据集合相关联的操作集

$\cdot$ 抽象：描述数据类型的方法不依赖于具体实现

-与存放数据的机器无关
-与数据存储的物理结构无关
-与实现操作的算法和编程语言均无关

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

抽象：不管你怎么加的，先加列还是行

1.2 什么是算法

1.2.1 定义

依然很抽象!

好的算法：


不断函数调用，占用的空间与N相关

而循环实现的程序，由于它只用了临时变量和一个for循环，没有涉及任何程序调用的问题，所以不管那个N有多大，占用的空间始终是一个固定的。占用空间的量（是一个常量）不会随着N的增长而增长。

分析函数运行效率，看函数做了多少次乘法（加减法比乘除快很多）：

上面每一次循环执行i次乘法，下面一次循环一次乘法。

在分析的时候，通常分析 最坏情况复杂度，“平均”这一问题不是很好搞定。

1.2.2 复杂度的渐进表示

没必要数每个操作做了多少次，只关心随着处理规模的增大，复杂度增长的性质和趋势。

O上界，Ω下界。

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

复杂度O(N^3)。该算法有三层嵌套的for循环，第一个0到N，第二个id到N，第三个i到j，整个的运算量是N立方乘以一个常数。

但是当我们知道当前从i到j的和的时候，我们要计算下一个j的时候，没有必要从头开始往后加。当j增加1时，其实只要在前面的那个i到j的部分和后面加1个元素就行。完全没有必要要那个k循环，是多余的。

有没有可能把O(N^2)改进成NlogN呢？

算法3：分而治之

复杂度：

这让然不是最快的算法！

一个算法的效率这么高，是有副作用的：它的正确性不是特别地明显。理解起来困难！

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