目录
? ? ? ? 本文纯纯是自己复习知识写的，如果这个对大家有用的话我很开心~~~。
研究内容
????????研究计算机的操作对象以及他们之间的关系和操作。(针对非数值计算的程序设计问题！)
????????涵盖内容：
基本概念
????????数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。
数据
????????所有能被计算机识别、存储和处理的符号集合。(程序处理的对象)
????????分类：数值数据、非数值数据
数据元素
????????是数据的基本单位。
????????数据项是构成数据元素的最小单位。
数据对象
????????具有相同性质的数据元素的集合，是数据的一个子集
数据结构
????????相互之间存在一种或多种特定关系的数据元素的集合。
????????Data_Structure = (D,R)
数据类型
????????一个值的集合和定义在该值上的一组操作的总称。
抽象数据类型(ADT)
????????用户定义的数据模型与定义在该模型上的一组操作，由基本的数据类型构成。
????????(抽出问题本质特征而忽略了细节，不考虑数据项的操作)
数据结构在逻辑上的分类
- 集合：数据元素之间没有关系
- 线性结构：数据元素之间一对一的线性关系
- 树结构：数据元素之间一对多的层次关系
- 图结构：数据元素之间多对多的任意关系? ? ? ? ? ??
算法
定义
????????对特定问题求解步骤的一种描述，是指令的有限序列，是一系列输入转换为输出的计算步骤。
（算法不是答案！！！是步骤！！！）
基本特性
????????输入、输出
- 有穷性：总在执行有穷步后结束，且每一步在有穷时间内完成。(不是无限循环也不是数学概念)
- 确定性：每条指令都有确切的含义，不存在二义性。
- 可行性：通过已实现的基本操作执行有限次。
好算法的设计要求：
- 正确性：满足问题需求，对于任何合法输入算法都有正确结果。
- 可读性?：易理解易实现。
- 健壮性：对于非法输出的抵抗能力。
- 效率与低存储量需求
描述方法：自然语言、流程图、程序设计语言、伪代码。
算法分析
时间复杂度
????????问题规模充分大时，算法中基本语句执行次数在渐近意义下的阶。(是一种估算技术)
? ? ? ? 记为：O
?
空间复杂度
? ? ? ? 算法在执行过程中需要的辅助空间数量，除算法本身输入输出数据所占用的空间外，算法临时开辟的存储空间。
? ? ? ? 若辅助空间相对于问题规模来说是一个常数，则称算法为原地(就地)工作，否则为问题规模的函数：S(n) = O(f(n))。
? ? ? ? 非递归算法：O(1):常量阶、O(n):线性阶、平方阶、立方阶、对数阶
? ? ? ? 递归算法：扩展扩展再扩展
? ? ? ? 最好、最坏和平均情况：
????????????????如顺序查找第一个元素，一次比较每一个元素，直到找到k位置。
? ? ? ? ? ? ? ? *若数组第一个元素为k，那么只要比较1次，这就是最好情况！
? ? ? ? ? ? ? ? *若数组最后一个元素为k，那么就要比较n次，这就是最坏情况！
? ? ? ? ? ? ? ? *设数据等概率分布，那么平均要比较n/2次，这是平均情况。
? ? ? ? ? ? ? ? 一般来说，最好情况不能代表算法性能！发生概率较小。
? ? ? ?
????????? ? ? ? ? ? ? ? ? ??