程序核心数据结构与算法

数据结构学科的定义：主要是为研究和解决如何使用计算机处理非数值问题而产生的理论、技术和方法。
数据结构：
是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构由数据元素依某种逻辑关系组织起来，在数据结构上需要定义一组操作（运算）。

1. 数据：是信息的载体,是计算机加工处理的对象.
2. 数值数据和非数值数据
   (1)数值数据：包括整数、实数或复数。主要用于工程计算、科学计算。
   (2)非数值数据：包括字符、文字、图形、图象、语音等。
   用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。
3. 数据元素：组成数据的基本单位。
   一个数据元素可以由若干个数据项组成。
   数据项是数据不可分割的最小单位。

1、数据元素间的逻辑关系
2、基本的逻辑结构
集合结构：结构中的元素之间除了“同属于一个集合”的关系外，别无其它关系；
线性结构：结构中的数据元素之间存在一对一的关系。
树形结构：结构中的数据元素之间存在一对多的关系；
图结构：结构中的数据元素之间存在多对多的关系。

3KEHXP((PY7UKZXV5C4LKZP.png

3.数据结构包括以下四个方面：
一：数据元素及特性：
是数据结构中的最基本信息单元。
二：数据的逻辑结构：
对数据元素间的逻辑关系的描述。
三：数据的存储表示（存储结构）
物理结构：是指数据的逻辑结构在计算机中的存储形式。
数据在计算机内的组织方式
四：运算的定义和算法
数据结构上的执行的运算和实现
1.2 数据抽象和抽象数据类型
抽象：抽取事物的共同的和实质的东西，忽略其非本质的细节。
数据结构抽象为一种聚集结构
聚集结构：
图结构：图和网
集合结构：集合和字典
树形结构：树、二叉树、堆、优先权队列
线性结构：线性表、堆栈、队列、字符串、数组、文件。

数据结构可分成以下两部分：
(1)数据结构的规范：
逻辑结构和运算的定义
(2)数据结构的实现：
存储结构和运算算法实现
规范指明：做什么
实现解决：怎样做

image.png

数据结构和算法是战场中的兵法。
码农是指挥作战的将军，代码是士兵和武器。
算法就是独立存在的一种解决问题的方法和思想。
算法的特性：
1、输入:算法具有0个或多个输入
2、输出：算法至少有1个或多个输出
3、有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤都可以在可接受的时间内完成
4、确定性：算法中的每一步都有确定的含义 不会出现二义性
5、可行性：算法的每一步都是可行的 也就是说每一步都能够执行有限的次数完成

(1) 正确性 算法的执行结果应当满足预先规定的功能和性能要求。
(2) 简明性 一个算法应当思路清晰、层次分明、简单明了、易读易懂。
(3) 健壮性 当输入不合法数据时，应能做适当处理，不至于引起严重后果。
(4) 效率 有效使用存储空间和有高的时间效率。
(5) 最优性 解决同一个问题可能有多种算法，应进行比较，选择最佳算法。

算法的空间复杂度：是程序运行从开始到结束所需的存储空间。
存储空间分为：固定部分：常量、简单变量。与问题的实例的特征无关的。
可变部分：算法在某次执行中处理的特定数据的大小和规模有关。
两个含有100个元素的数组相加与含有10个元素的数组相加。
排序的算法中元素的个数可视为该实例的特征。

算法的时间复杂度：是程序运行从开始到结束所需的时间

执行时间反应算法效率：

一个问题的解决可能有多个解决算法，但是程序执行的时间却相差很多，由此判断：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。
但是如果设备性能低下，两个算法的程序运行时间大致会相同，因此单纯依靠运行运行的时间来比较算法的优劣并不一定是客观准确的。
程序的运行离不开计算机环境(硬件和操作系统)。

QQ图片20180704214108.jpg.png
QQ图片20180704214058.jpg.png
QQ图片20180704214614.jpg.png

假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，有多少个基本操作就代表会花费多少时间单位。对于不同的机械环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，忽略机械环境影响而客观的反应算法的时间效率。

每台机器执行的总时间不同，但是执行基本运算数量大体相同

“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c*g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n) = O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度收到函数g的约束，亦即函数f与函数g的特征相似。

时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)

最重要的是其数量级和趋势。大O表示法 例如n的三次方。100n^3和8n^3。

算法完成工作最少需要多少基本操作：即最优时间复杂度&＃8211;理想状态，无参考价值
算法完成工作最多需要多少基本操作：即最坏时间复杂度&＃8211;一种保证，算法在此种程度的基本操作中一定能完成工作。
算法完成工作平均需要多少基本操作：即平均时间复杂度&＃8211;全面评价，算法性质，因为应用算法的实例分布可能并不均匀而难以计算。
因此关注最坏时间复杂度。

1.基本操作，即只有常数项，认为其时间复杂度为O(1)
2.顺序结构，时间复杂度按加法进行计算
3.循环结构，时间复杂度按乘法计算
4.分支结构，时间复杂度取最大值。
5.判断一个算法的效率时，往往只需要关注操作数量的最高此项，其它次要项和常数项可以忽略
6.在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。

常见时间复杂度

执行次数函数举例 阶 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n2+2n+1 O(n2) 平方阶
5log2n+20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlogn阶
6n3+2n2+3n+4 O(n3) 立方阶
2n O(2n) 指数阶
注意，经常将log2n（以2为底的对数）简写成logn
O(1)

数据结构

数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。
数据结构解决的问题：一组数据如何保存，保存形式。
内置数据结构，比如列表、元组、字典
扩展数据结构，比如栈，队列等

算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。
高效的程序需要在数据结构的基础上设计和选择算法。
程序 = 数据结构 + 算法
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。
数据运算的五种：插入、删除、修改、查找、排序

大话数据结构

算法的时间复杂度定义
在进行算法分析时，语法总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度。记作：T(n)=O(f(n)).它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称时间复杂度。其中f(n)是问题规模n的某个函数。大O记法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。