数据结构与算法概要_数据结构与算法的摘要

一.简介

数据结构是指数据之间存在一种或多种关系的数据集合，即数据与数据的关系

算法是被计算机使用来解决问题的的方法。可简单视为一系列解决问题的指令，算法代表着用系统的方法描述解决问题的策略机制。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

图灵奖 Pascal之父——Niklaus Wirth 提出 “程序 = 数据结构 + 算法”，可见其重要性

二.数据逻辑结构

数据元素与元素之间的关系可分为:
1.线性（Linear 一对一）

2.树型（Tree 一对多）

3.图（Graph 多对多）

4.集合
数据元素与元素之间没有相互关系，类似数学中的集合特性

三.数据存储结构

1.顺序存储

顺序存储结构的内存地址是连续的，插入、删除时需要移动数据后面数据，但随机访问性能较好

2.链式存储

数据与数据之间使用指针建立关系，链式存储适用于在较频繁地插入、删除。

四.算法特征

1.有穷性：算法必须能在执行有限个步骤之后终止

2.确切性：每一步骤必须有确切的定义

3.输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况

4.输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果

5.可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）

五.时间复杂度

算法的时间复杂度就是算法代码执行的时间。如何不运行代码情况下知道时间复杂度，假定CPU执行一条指令的时间为t，则时间复杂度为算法执行指令规模的一个函数:

T(n) 表示代码执行的时间，n为数据集规模，f(n)是一个规模—时间函数。

O表示渐进上界记号，代表代码执行的时间的变化趋势，简称时间复杂度。当n趋向于很大时，常数项的影响微乎其微，所以常常将常公式中公式中的低阶、常量、系数三部分去掉。

常见复杂度量级：

常量阶O(1)

线性阶O(n)

线性对数阶O(nlogn)

阶乘阶O(n!)

N次方阶O(n^N)

指数阶O(2^n)