数据结构与算法概述

数据结构,是相互之间存在一种或者多种特定关系的数据元素的集合。

数据结构研究非数值计算程序设计问题中的操作对象,以及它们之间的关系和操作。

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,每条指令表示一个或多个操作。

程序设计 = 数据结构 + 算法。

基本概念

数据

数据是描述客观事物的符号,是能够被计算机识别、处理并输出的符号集合。

数据元素

数据元素是组成数据的、有一定意义的基本单位,在计算机中通常作为整体来处理,比如人、汽车。

数据项

数据元素由若干个数据项组成,数据项是不可分割的最小单位,比如人的性别、年龄。

数据对象

数据对象指性质相同的数据元素的集合,是数据的子集,比如同一个班级的 60 名学生。

数据类型

数据类型指一组性质相同的值的集合以及定义在此集合上的操作的总称,比如整型、字符型。

抽象数据类型

Abstract Data Type,ADT,指一个数学模型(数据元素间的逻辑关系)及定义在该模型上的一组操作,取决于逻辑特性,与在计算机内部的表示和实现无关。

逻辑与物理结构

按照关注点的不同,数据结构可以分为逻辑机构和物理结构。

逻辑结构

逻辑结构指数据对象中各数据元素之间的逻辑关系,分为以下 4 种:

  • 集合结构 —— 数据元素除了同属于一个集合外无其他关系
  • 线性结构 —— 数据元素之间是一对一的关系
  • 树形结构 —— 数据元素之间存在一对多的层次关系
  • 图形结构 —— 数据元素是多对多的关系

物理结构

物理结构指数据的逻辑结构在计算机中的存储形式,也叫存储结构,分为以下 2 中:

  • 顺序存储结构

数据存储在地址连续的存储单元中,逻辑关系与物理关系一致。

  • 链式存储结构

数据元素存放在任意的存储单元中,可以连续也可以不连续,物理关系不能反映其逻辑关系,需要通过指针存放数据元素的地址,以找到相关数据元素的位置。

算法的特性

算法具有以下 5 个基本特性:

  • 有零个或多个输入
  • 有至少一个输出
  • 有穷性,即算法在执行有限的步骤之后结束,且每个步骤在可接受的时间内完成
  • 确定性,即每个步骤有确定的含义,不会出现二义性
  • 可行性,即每个步骤都是可行的,且每一步都能通过执行有限次数完成

算法设计的要求

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

  • 正确性,算法至少应该能正确反映问题,并能够得到正确答案
  • 可读性,好的算法应易于阅读、易于理解
  • 健壮性,当输入不合法时,算法能够做出恰当的处理
  • 时间效率高,尽可能缩短执行时间
  • 存储量低,占用尽可能少的存储空间

算法效率的度量

由于 事后统计 存在 必须编写程序、依赖软硬件环境、测试数据设计困难等缺点,所以通常采用 事前分析估算 的方法来评估算法的执行效率。

程序运行的耗时主要取决于算法、编译后的代码质量、问题输入规模、机器执行指令的速度等因素,抛开外部因素,程序的运行时间依赖于 算法的好坏问题的输入规模

时间复杂度

算法执行时,语句的总执行次数(总执行时间)T(n) 是关于问题规模 n 的函数,记作 T(n) = O( f(n) ) 。问题规模 n 增大,执行时间的增长率与 f(n) 的增长率相同,即算法的渐进时间复杂度,简称时间复杂度,通常使用 O() 来表示。

计算时间复杂度时,只保留最高阶项,同时去除这个项的系数,如 f(n) = $4n^{4}$ +3n + 2 的时间复杂度为 O($n^{4}$) 。

常见的时间复杂度所耗费的时间有小到大依次为:

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

分析算法的时间复杂度,关键是分析循环结构的运行情况。

平均运行时间是算法的期望运行时间,而最坏情况运行时间是一种保证,通常提到的运行时间都指最坏情况的运行时间。

空间复杂度

算法的空间复杂度与时间复杂度类似,表示随问题规模 n 增长而所需的存储空间,S(n) = O( f(n) )

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2016-2020 姜越

谢谢老板

支付宝
微信