数据结构|第一章.概论数据结构|数据结构

- 1.1 什么是数据结构
- 1.2 术语定义
- 1.3 抽象数据类型
- - 1.4 算法定义
  - 1.4 时间复杂度和空间复杂度
  - - 时间复杂度
  - 空间复杂度

1.1 什么是数据结构

文章图片

数据结构，直白地理解，就是研究数据的存储方式。
我们知道，数据存储只有一个目的，即为了方便后期对数据的再利用，就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的加和值，无缘由的数据存储行为是对存储空间的不负责任。
因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容。
例如，一直以来大家面对的数据存储，都是类似存储 1、2、{a,b,c}、“http://data.biancheng.net” 这样的问题，解决方式无疑是用变量或者数组对数据进行存储，即：

int a=1; int b=2; char str[3]={'a','b','c'}; char *data="http://data.biancheng.net";

但是，如果要存储这样一组数据：{张亮，张平，张华，张群，张晶，张磊}，数据之间具有这样的关系：张亮是张平、张华和张群的父亲，同时张平还是张晶和张磊的父亲，数据之间的关系如图 1 所示：

文章图片

对于存储之间具有复杂关系的数据，如果还是用变量或数组来存储（比如用数组存储 {“张亮”,“张平”,“张华”,“张群”,“张晶”,“张磊”} ），数据存储是没有问题，但是无法体现数据之间的逻辑关系，后期根本无法使用，显然不明智。

针对此类数据，数据结构中提供有专门的树结构来存储这类数据。

再比如，导航无疑是出游旅行的必备神器，在我们程序员眼中，无论是哪款导航软件，其导航功能的实现都需要大量地图数据的支持。很明显，这些数据绝不是使用变量或数组进行存储的，那样对于数据的使用简直是个悲剧。

针对此类数据，数据结构提供了图存储结构，专门用于存储这类数据。

通过以上两个示例可以体会出，数据结构教会我们的绝不仅仅是如何存储 1、2、{a,b,c} 这样简单的数据，而是解决具有复杂关系的大量数据的存储问题。
因此，数据结构是什么? 我认为，数据结构是一门学科，它教会我们“如何存储具有复杂关系的数据更有助于后期对数据的再利用”。

即使解决一个非常简单的问题，往往也有多种方法，且不同方法之间的效率可能相差甚远

设计算法时，需要从以下三个角度分析来解决问题方法的效率

跟数据的组织方式有关
跟空间的利用效率有关
跟算法的巧妙程度有关

1.2 术语定义

数据对象：计算机要处理的事物，如“图书” 。
操作：处理事物的动作集合，如：增删改查排序。
算法：操作的实现方法，如：按字母序排放的“查找”和“插入”、“直接法”和“秦九韶法”的比较等。
通常一个算法用一个函数来实现。
逻辑结构：数据对象的逻辑组织关系。分为“线性”、“树”和“图”。
物理结构：数据对象信息在计算机内存中的存储组织关系。一般分为“顺序存储”和“链式存储”。

1.3 抽象数据类型

数据类型：数据对象的类型确定了其“操作集”和“数据定义域”。
抽象数据类型： “抽象”的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象集和操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。

1.4 算法定义
一个算法是解决某一类问题的步骤的描述。一般而言，算法应该符合以下五项要求：

输入：它接受一些输入（有些情况下不需要输入）
输出：至少产生一个输出
确定性：算法的每一步必须有充分明确的含义，不可以有歧义
有限性：算法是一个有限指令集，并一定在有限步骤之后终止
可行性：算法的每一步必须在计算机能处理的范围之内

1.4 时间复杂度和空间复杂度
在学习具体的数据结构和算法之前，每一位初学者都要掌握一个技能，即善于运用时间复杂度和空间复杂度来衡量一个算法的运行效率。
所谓算法，即解决问题的方法。同一个问题，使用不同的算法，虽然得到的结果相同，但耗费的时间和资源肯定有所差异。就比如拧一个螺母，扳手和钳子都可以胜任，但使用钳子拧螺母肯定没有扳手的效率高。
那么，如何衡量一个算法所编写出程序的运行效率呢？数据结构中，用时间复杂度来衡量程序运行时间的多少；用空间复杂度来衡量程序运行所需内存空间的大小。
时间复杂度判断一个算法所编程序运行时间的多少，并不是将程序编写出来，通过在计算机上运行所消耗的时间来度量。原因很简单，一方面，解决一个问题的算法可能有很多种，一一实现的工作量无疑是巨大的，得不偿失；另一方面，不同计算机的软、硬件环境不同，即便使用同一台计算机，不同时间段其系统环境也不相同，程序的运行时间很可能会受影响，严重时甚至会导致误判。
实际场景中，我们更喜欢用一个估值来表示算法所编程序的运行时间。所谓估值，即估计的、并不准确的值。注意，虽然估值无法准确的表示算法所编程序的运行时间，但它的得来并非凭空揣测，需要经过缜密的计算后才能得出。
也就是说，表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。
那么，如何预估一个算法所编程序的运行时间呢？很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。
以一段简单的 C 语言程序为例，预估出此段程序的运行时间：

for(int i = 0 ; i < n ; i++)//<- 从 0 到 n，执行 n+1 次 { a++; //<- 从 0 到 n-1，执行 n 次 }

可以看到，这段程序中仅有 2 行代码，其中：

for 循环从 i 的值为 0 一直逐增至 n（注意，循环退出的时候 i 值为 n），因此 for 循环语句执行了 n+1 次；
而循环内部仅有一条语句，a++ 从 i 的值为 0 就开始执行，i 的值每增 1 该语句就执行一次，一直到 i 的值为 n-1，因此，a++ 语句一共执行了 n 次。
因此，整段代码中所有语句共执行了 (n+1)+n 次，即 2n+1 次。数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。

再举一个例子：

for(int i = 0 ; i < n ; i++)// n+1 { for(int j = 0 ; j < m ; j++)// n*(m+1) { num++; // n*m } }

读者可结合注释，计算此段程序的频度为：(n+1)+n*(m+1)+nm，简化后得 2nm+2n+1。值得一提的是，不同程序的运行时间，更多场景中比较的是在最坏条件下程序的运行时间。以上面这段程序为例，最坏条件即指的是当 n、m 都为无限大时此段程序的运行时间。
要知道，当 n、m 都无限大时，我们完全就可以认为 n==m。在此基础上，2nm+2n+1 又可以简化为 2n2+2*n+1，这就是此段程序在最坏情况下的运行时间，也就是此段程序的频度。
思考一个问题，类似 2n+1、2n2+2n+1 这样的频度，还可以再简化吗？答案是肯定的。
以 2n+1 为例，当 n 无限大时，是否在 2n 的基础上再做 +1 操作，并无关紧要，因为 2n 和 2n+1 当 n 无限大时，它们的值是无限接近的。甚至于我们还可以认为，当 n 无限大时，是否给 n 乘 2，也是无关紧要的，因为 n 是无限大，2*n 也是无限大。
再以无限大的思想来简化 2n2+2n+1。当 n 无限大的：

首先，常数 1 是可以忽略不计的；
其次，对于指数级的 2n2 来说，是否在其基础上加 2n，并无关紧要；
甚至于，对于是否给 n2 乘 2，也可以忽略。
因此，最终频度 2n2+2n+1 可以简化为 n2 。

也许很多读者对于“使用无限大的思想”简化频度表达式，并不是很清楚。没关系，这里给大家总结一下，在数据结构中，频度表达式可以这样简化：

去掉频度表达式中，所有的加法常数式子。例如2 n 2 + 2 n + 1 2n^{2}+2n+1 2n2+2n+1 简化为2 n 2 + 2 n 2n^{2}+2n 2n2+2n ；
如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如2 n 2 + 2 n 2n^{2}+2n 2n2+2n 简化为2 n 2 2n^{2} 2n2；
如果最高项存在系数，且不为 1，直接去掉系数。例如2 n 2 2n^{2} 2n2 系数为 2，直接简化为n 2 n^{2} n2 ；

事实上，对于一个算法（或者一段程序）来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数。例如 2n+1 最简为 n，实际上就是 a++ 语句的执行次数；同样2 n 2 + 2 n + 1 2n^{2}+2n+1 2n2+2n+1 简化为n 2 n^{2} n2，实际上就是最内层循环中 num++ 语句的执行次数。

得到最简频度的基础上，为了避免人们随意使用 a、b、c 等字符来表示运行时间，需要建立统一的规范。数据结构推出了大 O 记法（注意，是大写的字母 O，不是数字 0）来表示算法（程序）的运行时间。发展至今，此方法已为大多数人所采纳。
大 O 记法的表示方法也很简单，格式如下：

O(频度)

其中，这里的频度为最简之后所得的频度。

例如，用大 O 记法表示上面 2 段程序的运行时间，则上面第一段程序的时间复杂度为 O(n)，第二段程序的时间复杂度为O ( n 2 ) O(n^{2}) O(n2)。
如下列举了常用的几种时间复杂度，以及它们之间的大小关系：
O ( 1 ) 常数阶 < O ( l o g n ) 对数阶 < O ( n ) 线性阶 < O ( n 2 ) 平方阶 < O ( n 3 ) ( 立方阶 ) < O ( 2 n ) ( 指数阶 ) O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^{2})平方阶 < O(n^{3})(立方阶) < O(2^{n}) (指数阶) O(1)常数阶

注意，这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的平均时间复杂度。

空间复杂度
和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。
要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：

程序代码本身所占用的存储空间；
程序中如果需要输入输出数据，也会占用一定的存储空间；
程序在运行过程中，可能还需要临时申请更多的存储空间。

首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。
程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。
事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。
举个例子：