前言

用本文记录自己学习数据结构开始

1.数据结构的基本概念

1.1基本术语

数据

数据是信息的载体,是描述客观事务的属性.
数据元素

数据元素是数据的基本单位,通常当做一个整体
数据对象

数据对象是具有相同类型的数据元素的集合

1.2数据结构的三要素

1.2.1数据的逻辑结构

逻辑结构是值数据元素之间存在逻辑关系,即从逻辑上表述数据,它与数据的存储无关,同时数据的逻辑结构分为线性结构和非线性结构,例如线性表的典型的线性结构,而集合,书,图是典型的非线性结构,大致分类如下图1.1

集合结构中的数据元素之间除了 “同属于一个集合”的关系外，别无其他关系。
线性结构结构中的数据元素之间只存在一对一的关系。
树形结构结构中的数据元素之间存在一对多的关系。
图状结构或网状结构结构中的数据元素之间存在多对多的关系。

1.2.2数据的存储结构

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。
索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。其优点是检索速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。其优点是检索、增加和删除结点的操作都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

1.2.3数据的运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

2.算法是什么

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法具有以下的5个特性:

有穷性:一个算法必须在有穷步之后结束,且每一步都可在有穷时间内完成
确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得到相同的输出
可行性:算法中描述的操作都可以通过已经实现的基本运行执行有限次来实现
输入:一个算法有0个或多个输入,这些输入取自与某个特定的对象集合
输出:一个算法有1个或者多个输出,这些输出是与输入有着某种特定关系的量

2.1算法效率的度量

算法效率的度量是由时间复杂度和空间复杂度来描述的

2.1.1时间复杂度

算法的时间复杂度，是一个用于度量一个算法的运算时间的一个描述，本质是一个函数，根据这个函数能在不用具体的测试数据来测试的情况下，粗略地估计算法的执行效率，换句话讲时间复杂度表示的只是代码执行时间随数据规模增长的变化趋势。

算法中所有语句的频度之和记为T(n),它是算法规模n的一个函数,时间复杂度主要分析T(n)的数量级,而算法中基本运算(最深层循环的语句)的频度与T(n)是同数量级的,因此通常采用算法中基本运算的频度*f(n)*来分析算法的时间复杂度,记作: $T(n)=O(f(n))$

2.1.1.1时间复杂度如何计算

下面写几个例子

for (int i = 1; i < n; ++i) {
        x++;
    }

这样的几行代码,他一共会执行3n+1次也就是 $\mathrm{O}(1+3 \mathrm{~n})=\mathrm{O}(\mathrm{n})$ 但是对于我们的时间复杂度而言,我们是不看重n前面的系数,所以他实际上的时间复杂度为O(n)

我们可以用这个规律来看待时间复杂度的书写

T(n)是不是常数：

是：时间复杂度为O(1) ·
否：时问复杂度为O(保留T(n)的最高次项并且去掉最高次项的系数)

我们来看下面这个:

for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ++x;
        }
    }

这时这个算法的时间复杂度就达到了 $\mathrm{O}\left(\mathrm{n}^{2}\right)$

还有这个:

for (int i = 1; i <n ; ++i) {
        x++;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            x++;
        }
    }

当n无限大的时候,前面的那个n可以当做常量,这时的时间复杂度可以写做 ${O\left(n+n^{2}\right)=O\left(n^{2}\right)}$

常见量级有一下几种

常量级 $O(1)$

int x=0;
int y=1;
int temp=x;
x=y;
y=temp;

常见的赋值语句的时间复杂度就是 $O(1)$

对数级: $O(\log N)$

int i=1;
   while (i<n){
       i= i*2;
   }

我们可以假设在第k次的时候i=n,这时我们可以写出这样的等式

$2 \wedge k=n$

$k=\log N$

这样他的时间复杂度就是一个对数级

下面还有 $n \log N$ 的复杂度

$O(n \log N)$

for (int j = 0; j <n ; ++j) {
       int x=1;
       while (x<n){
           x=x*2;
       }
   }

以及nm的复杂度

$\mathrm{O}(\mathrm{nm})$

for (int j = 1; j <n ; ++j) {
        for (int k = 1; k <m ; ++k) {
            x++;
        }
    }

计算技巧

我们计算时间复杂度

找到一个基本操作(最深层的循环)
分析该基本操作的执行次数x与问题规模n的关系x=f(n)
x的数量级o(x)就是该算法的时间复杂度T(n)

加法规则: $O(f(n))+O(g(n))=O(\max (f(n), g(n)))$ 我们保留加法中最高阶的项

乘法规则: $O(f(n)) \times O(g(n))=O(f(n) \times g(n))$

常见的渐进复杂度为:

$\mathrm{O}(1)<\mathrm{O}(\log n)<\mathrm{O}(n)<\mathrm{O}(n \log n)<\mathrm{O}\left(n^{2}\right)<\mathrm{O}\left(n^{3}\right)<\mathrm{O}\left(2^{n}\right)<\mathrm{O}(n !)<\mathrm{O}\left(n^{n}\right)$