Print service provided by iDogiCat: http://www.idogicat.com/
home logo





Home > IT > Programming > 数据结构和算法

概述

计算机处理的对象原来全是数值,后来发展到包括字符、表格和图像等具有一定结构的数据。因此,必须分析待处理对象的特性及它们之间的关系,来编写更有效的程序。这就是数据结构和算法的发展背景。

基本概念

  • 数据(Data):计算机处理的对象
  • 数据元素(Data Element):数据的基本单位,如“树”的一个结点
  • 数据项(Data Item):组成一个数据元素的一个项目。比如对于数据元素“职员”,诸如“姓名”、“性别”、“出生日期”等则是组成该数据元素的数据项。当然,有些简单的数据元素(比如一个由字符串表示的“月份名称”列表),则不需要有数据项。
  • 数据对象(Data Object):性质相同的数据元素的集合,是数据的子集。
  • 数据结构(Data Structure):相互间存在某种或多种关系的数据元素的集合。数据元素间的关系成为“结构”(Structure)。

数据元素间的关系类型

  • 集合(Set):最松散的关系,仅仅是都属于同一个集合,除此之外无任何关系。
  • 线性结构:数据元素间存在一对一的关系。
  • 树形结构:数据元素间存在一对多的关系
  • 图状结构或网状结构:数据元素间存在多对多的关系。

DataStructure = (D, S)
其中:D为数据元素的有限集;S为D的关系的有限集。

数据结构在计算机中的两种形态

  • 逻辑结构:定义数据元素间的逻辑关系,是抽象出来的数学模型。
  • 存储结构(物理结构):包括数据元素的表示和其间关系的表示。
    • 顺序存储结构:借助元素在存储器中的相对位置来表示其间的逻辑关系(比如array,其存储顺序代表其一对一的先后关系)
    • 链式存储结构:借助只是元素存储地址的指针来表示其间的逻辑关系(比如linked list)

数据类型(Data Type):是一个值的集合和定义于此值的集合上的一组操作的总称,多定义于某种编程语言中。比如,对于整数类型,值的集合为所能表示的范围内的所有整数,操作包括加减乘除等。

抽象数据类型(ADT:Abstract Data Type):是指一个数学模型以及定义于此模型上的一组操作。抽象数据类型不但包括上述的基本数据类型外,还包括用户自己定义的类型。

ADT的分类

  • 原子类型(Atomic Data Type):该类型的变量的值不可分解,比如整数型、100以内的整数型等等。
  • 固定聚合类型(Fixed Aggregate Data Type):该类型的变量由固定数目的成分按某种结构组成,比如复数类型,是由两个实数组成。
  • 可变聚合类型(Variable Aggregate Data Type):该类型的变量由可变数目的成分组成,比如整数列表,其元素数可变。

ADT = (D, S, P)
其中:D为数据对象;S为数据关系,是D上的关系集;P为基本操作,是对D的基本操作集。

多态数据类型(Polymorphic Data Type):是指值的成分不确定的数据类型。比如列表,其值可以是整数,可以是字符串,可以是某种类的对象,等等。

算法(Algorithm):是对特定问题的求解步骤的描述,是指令的有限序列。具有五种重要特性:有穷性、确定性、可行性、输入、输出。

好的算法需要满足以下条件:

  • 正确性(Correctness)
  • 可读性(Readability)
  • 健壮性(Robustness)
  • 效率及低存储需求:就是运行速度快,占用内存低。

算法效率的度量方法

  • 事后统计法:精确,但受限于所用的计算机硬件和同时运行的其他程序的限制和干扰。
  • 事前分析估算法:更常用的方法。这种方法以运算工作量表示,表示为问题规模(通常用n表示)的函数。

算法效率的估算方法

算法由控制结构(顺序、分支和循环)以及原操作(固有数据类型的操作)构成。为了便于比较同一问题的不同算法,通常从算法中选取一种对所研究的问题来说是一种基本操作的原操作,并以该操作的重复执行次数作为算法的时间量度。该操作一个是重复执行次数和算法执行时间成正比(或比较强的正相关)的那个操作,多为最深层循环内的操作。

算法的时间量度记作

T(n) = O(f(n))
表示随着问题规模n的增大,算法执行时间的增长率和重复执行次数f(n)的增长率相同,称为算法的渐进时间复杂度(Asymptotic Time Complexity),简称时间复杂度。

例如,两个N x N的矩阵的乘法:

// c = a x b
循环:i从1到N
    循环:j从1到N
        c[i, j] = 0
        循环:k从1到N
            c[i, j] += a[i, k] * b[k, j]

对于上述算法,基本操作是两个矩阵元素的相乘并累加到结果中。它的执行次数是n的3次方,记作:

T(n) = O(n^3)

常见时间复杂度:

  • O(1):常量阶,复杂度不随问题规模而增长
++x;
  • O(n):线性阶,复杂度随问题规模线性增长
for(int i = 0; i < n, ++i)
    ++x;
  • O(n^2):平方阶
for(int i = 0; i < n, ++i)
    for(int j = 0; j < n, ++j)
        ++x;
  • O(log(n)):对数阶。比如二叉树搜索
  • O(2^n):指数阶

最佳的为常量阶,而指数阶则尽量避免。

同时,具体的执行时间还随着输入数据的不同而有差别,比如对于排序,如果输入是已经排好序的数据,则一般比顺序杂乱的数据费时要少。因此,对于事前估算,还有平均时间复杂度和最坏情况下时间复杂度两种。常用的是后者。

事前估算和事后统计的合并应用:比如已知矩阵乘法的时间复杂度为O(n^3),并实际测量10x10矩阵乘法的执行时间为T10,则可估算100x100矩阵乘法的执行时间为:T100 = T10 x (100/10)^3 。

空间复杂度(Space Complexity):算法所需存储空间的量度,记作

S(n) = O(f(n))

进阶阅读

  • 线性表
  • [[DataStructureNo2][]]
  • [[DataStructureNo3][]]
  • [[DataStructureNo4][]]
  • [[DataStructureNo5][]]
  • [[DataStructureNo6][]]
  • [[DataStructureNo7][]]
  • [[DataStructureNo8][]]
  • [[DataStructureNo9][]]
  • [[DataStructureNo10][]]