数据结构概述

  1. 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合
  2. 数据:描述客观事物的符号,能被计算机识别并操作的对象,能输入到计算机中进行处理的符号集合
  3. 数据元素:组成数据的基本单位,通常作为整体处理,也称为记录(着眼点)
  4. 数据项:一个数据元素可以由若干个数据项组成(最小单位,不能再分割)
  5. 数据对象:性质相同(即相同数量和类型的数据项)的数据元素的集合,是数据的子集
  6. 建模:建立模型,为了理解事物而对事物做出的一种抽象,是对事物的一种无歧义的书面描述
  7. 逻辑结构:指数据对象中数据元素之间的相互关系,针对具体问题来选择合适的数据结构表示数据元素之间的逻辑关系,有以下几种:
    • 集合结构:数据元素同属于一个集合
    • 线性结构:一对一的关系
    • 树形结构:一对多的层次关系
    • 图形结构:多对多的关系
  8. 存储结构(物理结构):数据的逻辑结构在计算机中的存储形式,有两种形式:
    • 顺序存储结构:把数据元素存放在地址连续的存储单元里
    • 链式存储结构:通过指针存放在任意的存储单元里,可以连续或不连续,更为灵活
  9. 数据类型:一组性质相同的值的集合及定义在这集合上的一些操作的总称,以C为例,分两类:
    • 原子类型:不能再分解的基本类型,包括整型、实型、字符型等
    • 结构类型:由若干个类型组合而成,可以再分解,比如整型数组等
  10. 抽象:抽取出事物具有的普遍性的本质(隐藏了繁杂的细节,只保留实现目标所必须的信息)
  11. 抽象数据类型(ADT):指一个数学模型及定义在该模型上的一组操作(取决于它的一组逻辑特性);一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作,它体现了程序设计中问题分解抽象信息隐藏的特性

算法概述

  1. 算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,每条指令表示一个或多个操作
  2. 好算法例子:实现n的累加 sum=(1 + n) * n / 2
  3. 基本特性:
    • 输入输出:可以有多个输入(0个也可), 但至少会有一个输出
    • 有穷性:执行了有限步骤后会自动结束而不是无限循环,每个步骤的时间合理
    • 确定性:每一步骤对具有确定的含义,不会出现二义性
    • 可行性:每一步都能够通过执行有限次数完成
  4. 算法设计应遵循:
    • 正确性:能正确够处理无歧义、反映出有效问题的需求,得到满足要求的结果
    • 可读性:便于阅读、理解和交流
    • 健壮性:当输入数据不合法时可以对其进行处理(得出满足规格说明的结果)
    • 高效率低存储:尽可能满足时间效率高、存储量
  5. 算法效率的度量方法:
    • 事后统计法:通过有计时功能的测试程序算出时间并进行比较,从而确定算法效率的高低 (不推荐)
    • 事前分析估算法:依据统计方法对算法进行估算,即f(x)=y, 依赖于算法好坏(f)问题输入规模(x)
  6. 函数的渐进增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么我们说f(n)的渐进增长快于g(n)
  7. 判断一个算法的效率时,函数中的常数次要项可以忽略,关注点是主项(最高阶项)的阶数
  8. 算法时间复杂度:即算法的时间量度,表达式为T(n)=O(f(n)),随着问题规模n的扩大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度(简称时间复杂度),O()大O记法
  9. 推导大O阶方法:用1取代所有常数;只保留最高阶项;去除与这个项相乘的常数(若存在最高阶且不是1)
  10. 常见时间复杂度:
    • 常数阶:O(1),执行时间恒定的算法;单纯的分支结构的时间复杂度为O(1)
    • 线性阶:O(n),分析循环结构的运行情况
    • 对数阶:O(logn),也常在循环中见;例如5log2n+20
    • 平方阶:O(n²),如2n²+3n+1
    • 还有立方阶、nlogn阶、指数阶
  11. 由小到大比较:O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)
  12. 最坏情况运行时间:即保底运行时间,一般所说的运行时间都是指最坏情况的运行时间;平均运行时间:即期望的运行时间,需要通过一定的估算
  13. 算法空间复杂度:表达式为S(n)=O(f(n)), f(n)是关于n所占存储空间的函数;若所需的辅助空间对于输入数据量而言是个常数,则称此为原地工作,空间复杂度为O(1)