数据结构期末复习（1）学科定义、组成、算法的定义、时间复杂度比较-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构期末复习（1）学科定义、组成、算法的定义、时间复杂度比较。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构的几个方面

逻辑结构的描述

逻辑结构

存储结构

数据运算

数据结构和数据类型

数据类型

抽象数据类型(ADT)

算法及其描述

什么是算法

算法分析

算法的设计目标

算法时间性能分析

计算算法频度

算法时间复杂度

简化的算法时间复杂度分析

数据结构学科定义：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据：描述客观事物的数值、字符以及所有能被机器处理的各种符号集合

数据元素：数据的基本单位（例如一个班级中的每个学生记录为一个数据元素），数据元素是组成数据的有一定意义的基本单位。数据元素通常由若干个数据项组成（学生记录的姓名、性别等都是数据项）

数据项：数据的最小单位，也称域

数据对象：描述相同性质数据元素的集合，数据的子集

数据结构：存在某种特定关系的数据元素的集合

数据结构 = 数据对象+结构（数据元素间的关系构成结构）

默认情况下数据结构中的数据都指的是数据对象

数据结构的几个方面

逻辑结构 --------- 逻辑层面（数据元素之间的逻辑关系）--独立于计算机

物理结构（存储结构） --------- 数据元素及其关系在计算机中的存储方式

数据运算 --------- 施加在数据上的操作

逻辑结构的描述

二元组

数据结构={D,R}
D：数据元素的集合

R: D中数据元素之间的关系，关系是使用序偶来表示的。

序偶是由两个元素x和y按一定顺序排列而成的二元组，记<x,y>。x是它的第一元素，y是它的第二元素。

x为y的前驱元素

y为x的后继元素

若某个元素没有前驱元素（称为开始元素）

若某个元素没有后驱元素（称为终端元素）
- 对称序偶
  
  若<x，y>∈r（r∈R），则<y，x>∈r（x，y∈D），可用圆括号代替尖括号，即(x，y)∈r。
图形

图形中的点表示数据元素，图形中的弧表示数据元素之间的关系

如果数据元素x和y之间的关系为<x,y>，则图形中有从x的点出发到y的点的一条弧

逻辑结构

按照数据元素之间相互关系的特性来分，可以分为

集合

线性结构（线性表、栈、队列）:若结构非空，则有且仅有一个开始元素和终端元素，并且所有元素最多只有一个前驱元素和一个后继元素。

树形结构：若结构是非空的，则有且仅有一个元素为开始元素（也称为根结点），可以有多个终端元素，每个元素有零个或多个后继元素，除开始元素外每个元素有且仅有一个前驱元素。

图状结构：若结构是非空的，则每个元素可以有多个前驱元素和多个后继元素。

存储结构

计算机中存储器存储数据的方式

逻辑结构 —映射—>存储结构

顺序存储结构:

所有元素存放在一片地址连续的存储单元中

逻辑上相邻的元素在物理位置上也是相邻的，所以不需要额外空间表示元素之间的逻辑关系。

链式存储结构：

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

通过指针域来反映数据元素的逻辑关系

数据运算

将数据存放在计算机中的目的是为了实现一种或多种运算。

运算包括功能描述（或运算功能）和功能实现（或运算实现）

前者是基于逻辑结构的，是用户定义的，是抽象的

后者是基于存储结构的，是程序员用计算机语言或伪码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。

注：同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。

数据结构和数据类型

数据类型

数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。

数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。

在程序设计语言提供的数据类型支持下，就可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。

抽象数据类型(ADT)

抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。

抽象数据类型 = 逻辑结构+抽象运算

表示：三元组 ADT = (D,S,P) D: 数据对象 S: D上的关系集 P: 加在D上的一组操作定义抽象数据类型时，可以使用以下形式： ADT 抽象数据类型名{ 数据对象：数据关系：基本操作： }

算法及其描述

什么是算法

算法：对特定问题求解步骤的一种描述，它是指令的有限序列

算法的五个重要特性

有穷性 --- 算法执行有限步骤后自动结束，每步在可接受的时间内完成

确定性 --- 对于每种情况下执行的操作，在算法中都有确定的含义，不会出现二义性。并且在任何条件下，算法都只有一条执行路径。

可行性 --- 每条指令都是可执行的

输入性 --- 零个或多个输入

输出性 --- 一个或多个输出

算法分析

算法的设计目标

正确性

可使用性

可读性

健壮性

高时间性能与低存储量需求

算法时间性能分析

算法由控制结构（顺序、分支、循环）和原操作（基本类型的操作+，-，*，/等）构成

算法执行时间取决于两者综合

在一个算法中，执行原操作的次数越少，其执行时间也就相对地越少；执行原操作次数越多，其执行时间也就相对地越多。

算法中所有原操作的执行次数称为算法频度，这样一个算法的执行时间可以由算法频度来计量。

计算算法频度

假设算法的问题规模为n，例如对10个整数排序，问题规模为n就是10。算法频度是问题规模n的函数，用T(n)表示。

算法执行时间大致等于原操作所需的时间×T(n)，也就是说T(n)与算法的执行时间成正比。为此用T(n)表示算法的执行时间。比较不同算法的T(n)大小得出算法执行时间的好坏。

例：
// 两个n阶方阵相加，求T(n)
void matrixadd(int[][] A,int[][] B,int[][] C,int n)
{  for (int i=0;i<n;i++)		//语句①  n+1
      for (int j=0;j<n;j++)		//语句②  n(n+1)
	  C[i][j]=A[i][j]+B[i][j];	//语句③  n^2
}
T（n）= n+1+n(n+1)+n2 = 2n2+2n+1 = O(n2)

算法时间复杂度

算法中执行时间T(n)是问题规模n的某个函数f(n),记作：T(n)=O(f(n))

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。

一般的

一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。

一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。

其余常用的算法时间复杂度还有平方阶O(n^2)、立方阶O(n^3)、对数阶O(log2n)、指数阶O(2^n)等。

各种不同算法时间复杂度的比较关系如下:

时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a ！ =0时，时间复杂度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此类推

eg:
(1)   for(i=1;i<=n;i++)         //循环了n*n次，是O(n^2)
            for(j=1;j<=n;j++)
                 s++;
(2)   for(i=1;i<=n;i++)         //循环了(n+n-1+n-2+...+1)≈(n^2)/2 是O(n^2)
            for(j=i;j<=n;j++)
                 s++;
(3)   for(i=1;i<=n;i++)         //循环了(1+2+3+...+n)≈(n^2)/2, 是O(n^2)
            for(j=1;j<=i;j++)
                 s++;
(4)
i=1;k=0;
while(i<=n-1)
{
k+=10*i;
i++;
}
//循环了
n-1≈n次，所以是O(n)
(5)
for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=j;k++)
            x=x+1;
循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3，是O(n^3)