走进算法和数据结构的大门

算法和数据结构

第一章、算法和数据结构

1、算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

1.1、算法特性:

• 有穷性 : 在有穷步之后结束，即必须在一定时间内结束
• 确定性 : 算法的每一步必须有确切的定义，即无二义性。
• 可行性 : 算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。
• 输入 : 一个算法具有0个或多个输入，这些输入取自特定的数据对象集合
• 输出 : 一个算法具有1个或多个输出

1.2、衡量算法的好坏的重要标准:

• 时间复杂度
• 空间复杂度

1.3、时间复杂度:

​ 假设有一根火柴10cm，这根火柴每3分钟燃掉1cm，那么这个火柴需要多久能够燃完?

​ 答案: 自然是3 × 10 = 30分钟 如果这根火柴是 n cm 那么就是 3 × n = 3n分钟

​ 那么就可以记作 T(n) = 3n n就是火柴的长度

定义如下:

若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值不等于0的常数，则称f(n)是T(n)的同数量级函数。

记作T(n) = O(f(n)),O为算法的渐进时间复杂度，简称为时间复杂度

``复杂度比较: 常数阶 O(1) < 对数阶O(logn) <线性阶O(n) <平方阶O(n^2)

引入:高斯数学家小时候的故事(故事情节有失偏颇，望以史鉴之)

在很久以前，有一个调皮蛋，天天影响老师的授课，在课堂上调皮捣蛋，于是，这个老师就给他出了一道题，想难住"熊孩子"，为了让他能够安静下来，这个题目就是从1加到100！老师以为这个小孩能够因此安静下来，但没想到，几分钟后，"熊孩子"就算出了答案:5050!

老师非常难以相信，哪怕是他也不可能这么快，于是啊，就看了高斯的计算步骤:

首先把1到100 这100个数字两两分组,如下:

1 + 100 = 101

2 + 99 = 101

3 + 97 = 101…

一共有多少组相同的结果和呢? 100 / 2 = 50组

所以我们可以这么来算:

(1+100)×100/2 = 5050

这个"熊孩子"就是德国著名的数学家、物理学家、天文学家、几何学家，他被世界的人誉为"数学王子"

2、数据结构

数据结构(Data Structure)，是对数据的组织、管理和存储结构。是指数据元素之间的关系称为数据结构。

数据元素是数据的基本单位。例如:学生表中的一个记录就可以称为是数据元素

2.1、数据结构分类

• 线性结构- 最简单的数据结构，包括数组、链表，栈、队列、哈希表等
• 树结构- 相对复杂的数据结构，有二叉树、红黑树、AVL平衡树、哈夫曼树等
• 图结构- 图的数据结构又比较复杂，是一种多对多的关联关系。
• 集合结构- 这是一种比较松散的结构，代表着元素的关系是属于同一个集合的。

2.2、空间复杂度

一个程序的空间复杂度是指程序从开始运行到结束所需的存储量。

程序运行所需的存储空间包括以下两个部分

• 固定部分。主要包括程序代码、常量、简单变量所占用的空间
• 可变部分。指的是空间的大小与算法在某次执行中处理的特定数据的大小和规模有关。

3.时间和空间的考虑

之所以衡量算法的优劣之分是时间复杂度和空间复杂度，根本原因就是计算机的运算速度和存储空间是有限的。

但是啊，我们不能如此双标，既要时间也要空间，其实也是很难做到的，正所谓鱼和熊掌不可兼得。

在绝大数情况下，我们更加优先考虑时间，而不是空间，因为我们宁愿花费出大的存储空间，也不愿降低计算机程序的执行速度。

3、检验自我

什么是算法？

什么是数据结构？

数据结构的分类？

什么是时间复杂度？

什么是空间复杂度？