目录

数据结构-绪论

数据结构

基本概念与术语

  • 数据
    • 能被计算机处理的符号的集合。
  • 数据元素
    • 数据的基本单位,比如一个学生的所有记录。
  • 数据对象
    • 相同性质的数据元素的集合,如整数数据对象就是所有整数的集合。
  • 数据类型
    • 值的集合 + 定义在该集合上的一组操作
  • 抽象数据类型
    • 数据对象,数据关系,基本操作集合的三元组,与具体实现无关。
  • 数据结构
    • 数据元素之间非孤立的关系,包括了:逻辑结构,存储结构,数据的运算

数据结构三要素

逻辑结构

逻辑结构即数据的抽象表示,与具体实现无关的。

  • 线性
    • 一般性
    • 受限性
      • 队列
    • 推广
      • 数组
      • 广义表
  • 非线性
    • 集合
      • 一般树
      • 二叉树
      • 有向图
      • 无向图

存储结构

即数据结构的物理结构,这是数据结构在计算中的实际表示,依赖于具体实现。

  • 顺序存储
    • 逻辑上相邻,物理上也相邻。
  • 链式存储
    • 逻辑上相邻,物理上并不相邻。
  • 索引存储
    • 物理位置存储在索引表中。
  • 散列存储
    • 物理位置由一个散列函数计算得到。

数据的运算

运算的定义针对逻辑结构,运算的功能针对存储结构。

算法

基本概念

特性

  • 有穷性
    • 算法必须在有限时间内完成
  • 确定性
    • 对于相同的输入都有相同的输出
  • 可行性
    • 算法必须由基本运算的有限次组合来描述
  • 输入
  • 输出

目的

  • 正确性
  • 可读性
  • 健壮性
    • 对于非法数据有适当的处理
  • 高效性

效率度量

效率的度量由时间与空间的复杂度共同描述。

时间复杂度

即执行算法需要消耗的时间。

  1. n
    • 问题的规模,复杂度都是关于问题规模的函数
  2. 语句频度
    • 该语句在算法中被重复执行的次数
  3. T(n)
    • 所有语句的频度
  4. f(n)
    • 基本运算的频度

因为所有T(n)与f(n)同数量级,所以使用T(n)来衡量算法的实际复杂度。记做T(n)=O(f(n)),这里的O记号表示的的是取f(n)的最大数量级。

对于时间复杂度还有一点非常非常重要的是,时间复杂度依赖于输入。根据输入的不同,一般我们会将时间复杂度分类三类来讨论:最坏时间复杂度,平均时间复杂度,最坏时间复杂度。一般我们考虑在最坏情况下的时间复杂度,即算法运行的上界。

常用的时间复杂度比较:
O(1) < O((log_2)n) < O(n) < O(n) < O(n(log_2)n) < O((n^2)) < O((n^3)) < O((2^n)) < O((n!)) < < O((n^n))

空间复杂度

即实现这样的算法需要的辅助空间的大小。

  1. S(n)
    • 空间复杂度记号

算法原地工作是指算法所需要的辅助空间是常量,即O(1)。

经典习题

1) 以下属于逻辑结构的是( )
A. 顺序表 B. 散列表 C. 有序表 D.单列表

答案:C
解析:分清楚逻辑结构和存储结构。

2) 下列函数的时间复杂度是( )

int func(int n){
    int i=0, sum=0;
    while(sum < n) sum += ++i;
    return i;
}

答案:O((sqrt n))
解析:

3) 以下说法错误的是()
A. 算法原地工作的含义是指不需要任何额外的空间
B. 相同规模n下,复杂度O(n)的算法在时间上总是优于复杂度O((2^n))
C. 所谓的时间复杂度是指最坏的情况下,估算算法执行时间的一个上界
D. 同一个算法,实现语言的级别越高,执行效率越低

答案:A
解析:

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!