本文主要内容是数据结构术语、算法描述和算法分析方法概述。

数据结构术语

数据(data)是描述客观事物的数、字符以及能输入计算机中并被计算机处理的符号的集合。数据元素(data element)是数据的基本单位。数据对象(data object)是具有相同性质的数据元素的集合,是数据的子集。

数据结构(data structure)指的是数据元素之间的逻辑结构、存储结构及其数据的抽象运算,即按某种逻辑关系组织起来的一组数据,再按一定的存储表示方式把它们存储在计算机的存储器中,并在这些数据上定义一个运算的集合。

  • 数据的逻辑结构指数据元素之间的逻辑关系。数据的逻辑结构可以被分为“线性结构”和“非线性结构”。
  • 数据的存储结构指数据元素及其关系在计算机内的存储方式。如向量中各元素按其逻辑关系顺序存储,称为“顺序存储结构”;如向量中各元素通过指针连接存储,称为“链式存储结构”。
  • 数据的运算,即对数据元素施加的动作。数据的运算是数据结构不可分割的一个方面,在给定逻辑结构和存储结构的情况下,定义的运算集合及其运算性质的变化可能导致完全不同的数据结构。

数据类型(data type)是一个值的集合和定义在这个值集上的操作的总称。数据类型在高级程序设计语言中可以分为两类,一类其值不可分解的称为“原子类型(非结构类型)”;另一类称为“结构类型”,其值由若干个分量构成按某种结构组成,它的分量可以是结构或是非结构的。通常,数据类型可以视为程序语言已实现的数据结构。

抽象数据类型(abstract data type, ADT)是抽象数据的组织和与之相关的操作,它是描述问题的模型。抽象数据类型的特点是将数据定义和操作进行封装,以实现信息的隐藏性。

算法描述

算法是对问题求解步骤的描述,是由若干条指令组成的有穷序列。

算法必须满足五个基本准则:

  1. 输入。算法开始前必须给其用到的变量初始化,算法的输入可以包含零个或多个数据。
  2. 输出。算法至少有一个或多个输出。
  3. 有穷性。算法中每一条指令的执行次数都是有限的,且均在有穷的时间内完成,即算法必须在执行有限步骤后结束。
  4. 确定性。算法中的每一条指令的含义都必须明确,无二义性。
  5. 可行性。算法中描述的操作均可通过有限次的基本运算得到实现。

如果一个程序对任何输入都不会陷入无限循环,则它就是一个算法。但程序必须依赖于计算机程序语言,而算法可以用自然语言、计算机程序语言、数学语言甚至是约定的符号语言进行描述。

算法分析

对算法进行评价时,需要考虑算法在一切合法输入的前提下,能否在有限的时间执行并得到正确的结果。除此之外,还需要考虑以下三点:

  1. 执行算法所耗费的时间,即时间复杂性
  2. 执行算法所耗费的存储空间,即空间复杂性
  3. 算法应易于理解、易于编程、易于调试,即可读性和可操作性

在需要考虑的若干要点中,最重要的是算法的时间复杂性。

时间复杂度 O(f(n))

算法执行所耗费的时间是算法内每条语句执行时间之和,每条语句的执行时间是该语句的执行次数与该语句执行一次所需时间的乘积。一般情况下,语句的执行次数是操作规模 n 的一个函数,即 f(n)

在进行算法分析时,语句总的执行时间量度 T(n) 是关于问题规模 n 的函数,进而分析 T(n)n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度,记作 T(n)=O(f(n))。它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。

大 O 记法是用 n 为基本参数,把复杂性或运行时间表达为 n 的函数。大 O 记法表示一个算法的时间复杂度上界。以 O(f(n)) 为例,表示当 n 增大时,运行时间至多将以正比于 f(n) 的速度增长。

大 O 阶常用推导方法:

  1. 用常数 1 取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是 1,则去除与这个项相乘的常数。

常见时间复杂度如下:

  • 常数阶 O(1)
  • 线性阶 O(n)
  • 平方阶 O(n^2)
  • 对数阶 O(logn)
  • nlogn 阶 O(nlogn)
  • 立方阶 O(n^3)
  • 指数阶 O(2^n)

按运行时间将常见时间复杂度从小到大排列:

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

关于具体的数据结构和算法的时间复杂度,将在介绍相关知识点时一并介绍。