1-数据结构和算法简介

数据结构是讨论计算机系统中 数据的组织形式 及其相互关系。 数据：客观事物采用计算机进行识别、存储和加工所进行的描述 结构：事物间的相互关系和约束 数据结构的基本单元是数据元素

数据结构的3个层次：①数据的逻辑机构； ②数据的存储结构； ③数据的运算( 操作集合)

①逻辑结构：

●线性结构：有且仅有一个开始元素和终点元素，且所有数据元素最多只有一个直接前趋和一个直接后继。 比如 线性表 ●非线性结构： 一个元素可能有多个直接前趋和多个直接后继。 比如 树结构 图结构

②存储结构：

反应数据元素在计算机中的存储方案 顺序存储、链接存储、索引存储、散列存储

③操作集合：

遍历：在数据结构的各个元素中移动，或查看所有元素 插入：往数据结构中 添加新的元素 更新：修改 或 替换数据结构中的 一个或多个元素 删除： 把指定的数据结构元素移除 查找：在数据结构中找寻满足一定条件的数据元素 排序：在保持数据结构中元素个数不变的前提条件下，把元素按照指定的顺序重新排列，排序一般是针对线性逻辑结构。

二、算法

指为解决特定问题 的 有穷操作规则 的集合。 算法的5个基本特性： ①有穷性：有始有终； ②确定性：算法操作的每一步，其顺序和内容都必须唯一确定； ③数据输入 ④数据输出：一个算法至少有一个已获得的 有效信息输出。 ⑤可行性：任一步操作都是可以付诸实践的。

算法点的效率 可分为 时间效率 和空间效率。 引入 时间复杂度 和空间复杂度的概念： ●空间复杂度：

除开存储数据结构本身外（比如指令、常数、变量 和输入数据），实现算法所需要的额外辅助空间有多少。 S（n）=O [ f(n) ] ●时间复杂度：

一般情况下，算法中 基本操作的重复执行次数 与问题规模n的某个函数f(n).

定性地描述了算法运行的时间。 T(n) = O[f(n)] ， 不考虑这个函数的 首项系数 和 低阶项。 相同规模的不同输入，仍可能导致算法的运行时间不同。一般使用算法最坏情况下的的复杂度来做代表。 时间复杂度可以用T(n)的自然特性加以区分，如： 常量时间O(1) 线性时间O(n) 指数时间O(n^2) 对数时间O(logn) O(1) < O( logN) <O( logN^2) < O(N) < O(N*logN) < O(N^2) < O(N^3)< ...<O(N^k) < O( 2^N) < O(3^N) < ... O(k^N) < O(N!)

常量时间：它表示某个算法求出解答的时间在固定范围内，而不依照问题输入数据规模变化。

比如：访问数组元素所需的时间为常量时间

程序= 算法 + 数据结构