数据结构和算法学习汇总

了解数据结构和算法的一些基本概念，主要掌握时间复杂度的计算

1、数据结构

1.1 定义

数据结构是指所有数据元素以及数据元素之间的关系，可以看做是相互之间存在着某种特定关系的数据元素的集合，即可以把数据结构看成是带结构的数据元素的集合。

1.2 包括

1. 数据元素之间的逻辑关系
   1. 即数据的逻辑结构
   2. 它是数据结构在用户面前呈现的形式
2. 数据元素及其在计算机存储器中的存储方式
   1. 即数据的存储结构
   2. 也称为数据的物理结构
3. 施加在数据上的操作(即数据的运算)

1.3 逻辑结构

1.3.1 介绍

数据的逻辑结构是从逻辑关系上描述数据的，常常将数据的逻辑结构简称为数据结构。

1.3.2 类型

集合：

• 集合中的所有元素除了同属于一个集合外，别无其他关系
  线性结构：
• 该结构中的节点之间存在一对一的关系。
• 其特点是开始节点和终端节点都是唯一的，除了开始节点和终端节点以外，其余节点都有且仅有一个前驱，有且仅有一个后继
• 线性表就是一种典型的线性结构

树形结构：

• 该结构中的节点之间存在一对多的关系
• 其特点是每个节点最多只有一个前驱，但可以有多个后继，切终端节点可以有多个
• 比如二叉树就是典型的树结构

图形结构：

• 该结构中的节点之间存在多对多的关系
• 其特点是每个节点的前驱和后继的个数都可以是任意的
• 因此图形结构可能没有开始节点 和终端节点，也可能有多个

1.3.3 注意

• 树形结构和图形结构统称为非线性结构，存在一对多或多对多关系。
• 线性结构是树形结构的特殊情况，树形结构是图形结构的特殊情况

1.4 逻辑结构

1.4.1 介绍

逻辑结构在计算机中的存储方式。依赖于计算机语言

1.4.2 类型

顺序存储结构：

• 该结构是把逻辑上相邻的节点存储在物理上相邻的存储单元里
• 节点之间的逻辑关系由存储单元的邻接关系来体现
• 优点是节省存储空间，便于查询，但是不便于增删

链式存储结构：

• 该结构不要求相邻的节点在物理上也相邻，起节点间的逻辑关系是由附加的指针字段来表示的
• 通常要借助指针类型来描述
• 因为数据的存储单元会有一部分用来存储节点之间的逻辑关系，所以浪费内存。
• 便于增删，但是不便于查询

索引存储结构：

• 需要建立附加的索引表
• 索引表存储有关键字和地址，地址就是指向节点的指针
• 可以高效的进行增删改查，只是会浪费一些内存用来建立索引表

散列（哈希）存储结构：

• 哈希结构是根据节点的关键字通过哈希函数直接计算出一个地址值，将其作为节点存储的位置
• 优点是查找速度快
• 哈希存储方式只存储节点的数据，不存储节点之间的逻辑关系。逻辑关系也不是靠物理地址判断的，而是通过节点的关键字进行哈希计算得到的
• 进行快速查找和插入的场合适合使用哈希存储结构

1.5 数据类型

数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称，数据类型是数据结构在计算机的具体体现。

注意：

• 对于一种数据结构，逻辑结构总是唯一的，但是他可能对应多种存储结构，并且在不同的存储结构中，统一运算的实现过程可能不同
• 针对数据的不同运算，为了适应运算的效率，采用了不同的存储结构

2、算法

算法是对特定问题求解步骤的一种描述

特性： 有穷性、确定性、可行性、有输入、有输出

2.1 介绍

算法设计好后，还需要分析算法的优劣，从两方面考虑

• 时间维度：执行当前算法所消耗的时间
• 空间维度：执行当前算法需要占用的内存空间

2.2 算法设计的目标

• 正确性：能够正确执行
• 可使用性：可方便使用
• 可读性：易于理解
• 健壮性：具有很好的容错性
• 高效率和低存储量需求：1）通常算法的效率主要指算法的执行时间；2）算法存储量指的是算法执行过程中所需的最大存储空间

2.3 时间复杂度

一个算法由控制结构和原操作构成，算法的运算时间取决于两者的综合效果，算法执行时间大致为基本运算时所需时间与运行次数的乘积。因此一个算法的执行效率可以由其最基本的运算的执行次数来衡量。

2.3.1 计算方式

计算公式： T(n)=O(f(n))

说明：

• 记号O读作大O
• 算法执行次数T(n)是问题规模n的某个函数f(n)
• 他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同

注意： O 的作用在于只求出T(n)的最高阶项，忽略低阶项和常数

2.3.2 常见时间复杂度

O(1)
没有进行循环的算法中，基本运算次数与问题规模无关，所以是常数

O(1).png

对数阶 Ｏ(log2n)
次数为x，而2的x次方等于n，那么就是对数阶

Ｏ(log2n).png

线性阶 Ｏ(n)
只有一层循环

Ｏ(n).png

平方阶 Ｏ(n^2)

• 可以看出只要有两层循环，不管第二层从几开始，都是n^2
• 因为加入第一层是(n-3),第二层执行了(n-6)，这样也是n^2

Ｏ(n^2).png

立方阶 Ｏ(n^3)
三层循环，肯定就是n^3了

Ｏ(n^3).png

排序：
Ｏ(1) < Ｏ(logn) < Ｏ(n) < Ｏ(nlogn) < Ｏ(n^2) < Ｏ(n^3) <Ｏ(2^n) < Ｏ(n!) < Ｏ(n^n)

2.3.3 期望时间复杂度

也叫加权平均时间复杂度，将执行的概率也加入计算。

2.3.3 均摊时间复杂度

是一种特殊的加权平均时间复杂度，把耗时多的操作分摊到耗时低的操作。

均摊时间复杂度.png

这个时间复杂度 其实是O(1),而不是O(n)

2.4 空间复杂度

算法空间复杂度是指计算算法所需的存储空间， 其计算公式为S(n) = n(f(n))
所以在考察算法的空间复杂度，主要考虑算法执行所需要的临时占用的存储空间大小的量度。

数组逆序,将一维v1.43数组a中的n个数逆序存放在原数组中.

复杂度计算:

空间复杂度计算.png

说明：

• 通过临时变量来做中间的交换：所需辅助空间为临时变量temp的空间，为O(1)
• 先倒序存入一个数组b，在从b中依序存入a：所需的辅助空间 为 O(n)