数据结构-基本概念

数据结构

在研究数据结构之前，我们有必要搞清楚什么是数据结构。

首先，什么是数据？

数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

而数据元素指的是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，例如：人、猫等。一个数据元素可以由若干个数据项组成，例如：人由眼睛、鼻子等组成，数据项是数据不可分割的最小单位。

对于数据元素中性质相同的集合，我们将其称为数据对象。在实际应用中，处理的数据元素通产具有相同的性质，在不产生混淆的情况下，将数据对象称为数据。

那么，什么是数据结构呢？

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构与物理结构

上文中说到，数据元素之间存在一种或多种特定的关系，依据关系类型的不同可以将数据结构分为逻辑结构和物理结构。

逻辑结构

逻辑结构是指数据对象中数据元素之间的相互关系，逻辑结构可以分为以下四种：

• 集合结构

  集合结构中的数据除了同属于一个集合外，它们之间没有其它关系。各个数据之间是相互平等的。

• 线性结构

  线性结构中的数据是一对一的关系。

• 树形结构

  树形结构中的数据之间存在一种一对多的层次关系。

• 图形结构

  图形结构的数据元素是多对多的关系。

逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。

物理结构

物理结构是指数据的逻辑结构在计算机中的存储形式。物理结构研究的就是如何将数据元素存储到计算机中，存储器主要是针对内存而言的。

数据的存储结构应该正确反映数据元素之间的逻辑关系，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

数据元素的存储形式有两种：顺序存储和链式存储。

• 顺序存储结构

  把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系一致。

• 链式存储结构

  把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

总的来说，逻辑结构是面向问题的，物理结构解决如何将数据元素之间的逻辑关系存储在计算机中。

算法

为了学好数据结构，就必须学习算法，只有同时掌握了数据结构和算法才能写出完整的程序。

何为算法？

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

• 输入、输出

  算法具有零个或多个输入，至少有一个或多个输出。

• 有穷性

  指算法在执行有限的步骤后，自动结束而不会陷入死循环，并且每一个步骤在可接受的时间内完成。

• 确定性

  算法的每一步骤都具有确定的含义，不会出现二义性。

• 可行性

  算法的每一步都必须可行，每一步都能够通过执行有限次数完成。

算法效率度量方式

在进行算法设计时，我们需要对算法的效率进行度量（大部分情况下指运行时间），那么如何对算法的运行时间进行度量呢？

一般存在两种度量方式，事后度量和事前度量，所谓事后度量，指的是设计测试程序和数据对程序的性能进行实地测试，但一个算法的运行效率和所使用的测试样例、硬件环境等有很大的关系，事后度量一般不准确。因而我们一般采用事前度量的方式。

一个用高级程序语言设计的程序在计算机上运行时所消耗的时间取决于下列因素：

• 算法采用的策略、方法。
• 编译产生的代码质量。
• 问题的输入规模。
• 机器执行指令的速度。

抛开与计算机硬件（第四条）、软件（第二条）相关的因素，一个程序运行的时间取决于算法的好坏和问题的输入规模。

而测定一个程序的运行时间的最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数，运行时间与这个计数成正比，如下述程序所示：

int i, j, x = 0, sum = 0, n = 100; /* 执行一次 */
for (i = 1; i <= n; i++)
{
4for (j = 1; j <= n; j++)
4{
44x++;
44sum = sum + x; /* 执行nxn次 */
4}
}
printf("%d", sum); /* 执行一次 */

在上述程序中，其最核心的基本操作便是两个for循环中的语句，该语句总计执行了nxn次。

在对算法效率进行分析的时候，我们不关心算法的实现语言是什么、实现平台是什么，只关注算法本身。不计循环索引的递增、循环终止条件、变量声明和打印等操作，在分析程序的运行时间时，最重要的是把程序看作是独立于程序设计语言的算法或一系列步骤。

我们要做的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。

函数的渐近增长

给出定义如下：

给定两个函数$f(n)$和$g(n)$，如果存在一个整数$N$，使得对于所有的$n>N$，$f(n)$总是比$g(n)$大，那么我们就说$f(n)$的增长渐近快于$g(n)$。

忽略加法常数

存在这样一种现象，随着输入规模的逐渐增大，算法计算效率中的加法常数所造成的影响将变得可以忽略不计。例如在对比$2n+3$和$3n+1$时，两者中的常数便可以被忽略。

忽略与最高次项相乘的常数

假如两个算法的计算效率分别是$4n+8$和$2n^2+1$，我们可以忽略掉其中的最高次项的常数系数，只保留$n$和$n^2$。

忽略低次项

在比较两个算法的计算效率时，我们可以忽略掉除最高次项的其它项，例如，$2n^2+3n+1$和$2n^3+3n+1$等价于比较$n^2$和$n^3$。

综合上述所言，我们可以得出这样一个结论：在判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

判断一个算法的优劣，我们无法只通过少量数据进行准确的判断。通过上述分析可以看出，如果我们可以对比这几个算法的关键执行次数函数的渐近增长性，基本就可以分析出：某个算法，随着$n$的增大，它会越来越优于另一个算法，或者越来越差于另一个算法。

这就是事前估计方法的理论依据，通过算法时间复杂度来估算算法时间效率。

算法时间复杂度

算法的时间复杂度的定义

算法的时间复杂度，也就是算法的时间度量，记作：$T(n)=O(f(n))$，它表示随问题规模$n$的增大，算法执行时间的增长率和$f(n)$的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中，$f(n)$是问题规模的某个函数。

上述使用大写的$O$表示算法的时间复杂度的记法，称作大$O$记法。

计算算法的大$O$阶

计算方法大体如下：

• 用常数1取代运行时间中的所有加法常数。

• 在修改后的运行次数函数中，只保留最高阶项，也就是只关注循环执行次数最多的一段代码。

  在分析一个算法、一段代码的时间复杂度时，只关注循环执行次数最多的那一段代码就行了。

• 如果最高阶项存在且不是1，则去除于这个项相乘的常数。

• 嵌套代码的时间复杂度等于嵌套内外代码复杂度的乘积。

  int cal(int n) {
     int ret = 0; 
     int i = 1;
     for (; i < n; ++i) {
       ret = ret + f(i);
     } 
   } 
   
   int f(int n) {
    int sum = 0;
    int i = 1;
    for (; i < n; ++i) {
      sum = sum + i;
    } 
    return sum;
   }

  上述代码的时间复杂度等于cal(int n)函数中for循环的时间复杂度$O(n)$乘以函数f(int n)的时间复杂度$O(n)$，即该段代码的时间复杂度为$O(n^2)$。

常数阶

存在这样一类算法，它们的计算复杂度与问题的输入无关，无论问题的规模为多少，这些算法的执行时间都是恒定的，我们称此类算法为具有$O(1)$的时间复杂度，又叫常数阶。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是$O(1)$。

线性阶

我们要分析算法的复杂度，关键就是要分析循环结构的执行情况。

int  i;
for (i = 0; i < n; i++)
{
4/* 时间复杂度为O(1)的程序步骤序列 */
}

上述程序的循环分支中的语句执行了$n$次，因此其时间复杂度为$O(n)$。

对数阶

如下述代码：

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

我们需要计算出上述代码中的while循环中的语句的执行次数，count每次乘2，满足$count*2^x=n$，即$x=log_2n$时循环结束，所以这个循环的时间复杂度为$log_2n$。

实际上，不论以2为底还是以3为底，都将所有对数阶的时间复杂度记为$O(logn)$。同时，如果一段代码的时间复杂度为$O(logn)$，将这段代码重复执行$n$次，时间复杂度就是$O(nlogn)$。

平方阶

当循环内部嵌套循环时，总的算法的时间复杂度为循环体的复杂度乘以该循环运行的次数。

ing i, j;
for (i = 0; i < m; i++)
{
4for (j = 0; j < n; j++)
4{
44/* 时间复杂度为O(1)的程序步骤 */
4}
}

上述算法的时间复杂度为$O(n^2)$。

$O(m+n)、O(m*n)$

这一类时间复杂度与前面几种复杂度不同，该类时间复杂度由两个数据的规模决定。如下述代码所示：

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

在上述代码中，$m$和$n$是两个数据规模，我们无法事先估计两者的量级大小，所以在计算时间复杂度时就无法利用加法规则省略掉其中的一个。但是此时乘法规则仍旧适用。

常见的时间复杂度

常见的时间复杂度如下表所示：

执行次数函数	阶	非正式用语
$12$	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2+2n+1$	$O(n^2)$	平方阶
$5log_2n+20$	$O(logn)$	对数阶
$2n+3nlog_2n+19$	$O(nlogn)$	$nlogn$阶
$6n^3+2n^2+3n+4$	$O(n^3)$	立方阶
$2^n$	$O(2^n)$	指数阶

上述时间复杂度所耗费的时间从小到大以此为：

$$O(1)<O(N)<O(n^2)<O(logn)<O(nlogn)<O(n^3)<O(2^n)$$

在算法复杂度的分析中，一般提到的运行时间都是最坏情况下的运行时间。

算法的空间复杂度

在进行算法设计时，我们完全可以使用空间换时间。算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：$S(n)=O(f(n))$，其中，$n$为问题的规模，$f(n)$为语句关于$n$所占存储空间的函数。同样，空间复杂度的全称为渐近空间复杂度。

通常情况下，我们使用“时间复杂度”指程序运行时间的需求，使用“空间复杂度”指空间需求。当不使用限定词时，“复杂度”通常都是指时间复杂度。

参考

• 《大话数据结构》
• 数据结构与算法之美-王争