算法的概念-入门精简笔记


算法的概念

算法与指令

  • 算法是有限指令集

  • 算法是对特定问题求解步骤的有限指令集

  • 指令表示计算机内的一个操作

五大特征

输入性:少数算法可以没有输入(例如:随机)

输出性:输出算法的结果

有穷性:有限时间内结束,能够结束,不能有死循环

确定性没有歧义

可行性:可以用计算机实现的,每条指令都是可执行的

算法的评价

时间复杂度复和空间复杂度算法是以宏观评价为主,微观为辅

时间复杂度

用来描述算法在执行过程中所需要的基本运算次数

  • 关键语句(基本/核心/最重要 语句)的执行次数
  • 不需要统计每条语句的执行时间
  • 将时间的长短转换为执行语句的总次数:最耗时间,至少是循环

易错点

  • 算法的时间复杂度 不是计算 算法的执行时间,要搞清楚
  • 算法的时间复杂度 与问题的规模、指令的数量 有关,与语句无关
关键指标 描述
平均时间复杂度 所有时间复杂度的平均值
最坏时间复杂度 所有时间复杂度的最大值
最优时间复杂度 所有时间复杂度的最小值

空间复杂度

又可称:空间的大小

指:算法在执行过程中所需要的计算机存储空间,执行时所占的内存

  • 包括常用空间临时空间
  • 算法执行时不使用外存空间
  1. 有一个循环,循环内5条语言,循环共执行100次,该循环部分的时间复杂度为()

    5 x 100 =500 (次)

  2. 从10个数字中查找一个数,指出最坏、最优、平均时间复杂度()

    最坏时间复杂度:10

    最优时间复杂度:1

    平均时间复杂度:(1+2+3..+10)/10 = 5.5

数据结构

数据结构由数据元素数据项组成

  • 数据元素数据的基本单位
  • 数据项数据的最小单位
  • 一个数据元素由多个数据项组成

也可以这样理解:

数据结构 = 数据 + 结构

数据结构=数据的集合+ 数据之间的关系(是否相邻的关系)的集合

元素之间的关系

两个元素之间:有关系(相邻),无关系(不相邻)

直接前驱直接后续(是一对的关系):

  • 春是夏的直接前驱
  • 夏是春的直接后继

数据结构的分类

数据结构分为:逻辑结构物理结构

  • 逻辑结构分为集合结构,线性结构,树型结构,图形结构
  • 非线性逻辑结构指的是逻辑结构和非物理结构

物理结构:指计算机中的结构(存储结构指的就是物理结构)

  • 逻辑结构在计算中表示
  • 先有逻辑后有物理

物理结构的分类:

  • 顺序存储结构
  • 链式存储结构
  • 索引存储结构
  • 散列存储结构

数据的存储结构对程序的执行效率影响很大,是最直接的影响因素

逻辑结构与物理结构的关系

  • 逻辑结构存在于大脑世界、物理结构存在于计算机内部
  • 先有逻辑结构后有物理结构
  • 他们不是一一对应的
  • 一种逻辑结构可以有多种物理结构

循环队列指就是将队列存储空间的最后一个位置链接到第一个位置,形成运算上的环状空间,供队列循环使用,所以,循环队列属于存储结构

线性结构

  • 有且只有一个 头节点
  • 有且只有一个 尾节点
  • 有且只有一个 根节点
  • 头节点外 每个节点有且只有一个 直接前驱
  • 尾节点外 每个节点有且只有一个 直接后继

如:一年4个季节

线性表

线性表属于线性结构:线性表是线性结构的一个具体实例,也就是线性表需要满足线性结构的基本特征

杂知识点

  • 向量空间一维空间
  • 计算机内部存储是向量式的(也就是0/1)
  • 数组空间也是向量式的,数组是顺序存储结构 但是数组可以处理非线性结构(二维数组)

顺序表

顺序表是 线性表的顺序存储结构(物理结构)

  • 优点:结构简单,运算简单
  • 缺点:插入删除效率低,长度固定
  • 所有空间必须连续
    • 必须逻辑上的连续:直接前驱,和直接后继 - (a是b的直接前驱,则b一定是a的直接后继)
    • 元素在物理存储空间上也必须连续

顺序表基本运算

插入运算

插入后元素之间存储关系必须要保持连续

  • 移动的方向:从尾元素开始移动,每个元素往后移一位
  • 时间复杂度:移动元素的个数

n个元素顺序表,在 I 号位置插入一个元素,移动元素个数为()

  • 时间复杂度:N-I+1
  • 最坏时间复杂度:N
  • 最优时间复杂度:0
  • 平均时间复杂度:(0+1+…N)/(N+1) = N/2
删除运算
  • 移动方向:从被删除的元素的下一个元素开始,往前移动
  • 时间复杂度:移动元素的个数

计算方法:n个元素顺序表,删除 I 号位置的元素,移动元素个数为()

  • 最坏时间复杂度:N-1
  • 最优时间复杂度: 0
  • 平均时间复杂度(从零开始): (0+1+2…+(N-1)) / N = (N -1) / 2

习题

题1:10个元素的顺序表,在7号位置插入一个元素,移动元素的个数为()。以及最坏、最优、平均时间复杂度为()

根据题意得出:

  • 从十号开始往后移动,所以时间复杂度为4
  • 最坏时间复杂度为:10
  • 最优时间复杂度为:0 (可在11号加,就不用移动了)
  • 平均时间复杂度:(0+1+2…+10)/11 = 5

题2:10个元素的顺序表,删除7号元素的位置,求事件复杂度、以及最坏、最优、平均时间复杂度为

根据题意得出:

  • 从8号开始往前移动,时间复杂度为3
  • 最坏时间复杂度:9
  • 最优时间复杂度:0
  • 平均时间复杂度:(0+1+2…+10)/10 = 4.5

线性链表

线性链表线性表链式存储结构(物理)的简称

  • 优点:空间上不要求连续,需要空间上可以动态分配,不要求固定
  • 线性表可以有多种存储结构
  • 尾节点的指针域为空

线性链表结构

每个元素存储空间分为2部分:

第一部分 第二部分
数据域 指针域
存放元素的值 存放元素之间的关系

双向链表

  • 双向链表每个元素有三个域(1个数据域和2个指针域)
  • 指针域保存直接前驱直接后继
  • 尾节点的指针域为空
双向链表的计算(不考)

和队列

队列 都属于线性结构

栈和队列都只能在端操作

  • 线性结构有2端,首端和尾端
  • 规定只能在1端操作
  • 队列规定在 2 端操作

栈:先进后出,后进先出(FILO)

  • 类似:桶(一端开,一端封闭)
  • 栈顶:可操作的端(可运算
  • 栈底:不可操作的端(不可运算
  • 入栈:插入元素
  • 出栈:删除元素
  • 栈和队列都是线性表

栈的运算:

题1:入栈顺序ABC,求出栈可能性()

  • 可能出现的顺序:CBA,ABC,ACB等
  • 不可能出栈的序列:CAB

题2:ABC一次入栈,然后出栈1次,123再入栈,最后全部出栈,出栈的顺序为()

根据题意得出:第一次出栈为C,压入123后,此时栈值为AB123。由于后进先出原则,所以逆向出栈

则:出栈顺序为 C321BA

队列

类似站队:一端进一端出,先进先出

  • 队头:出的端
  • 队尾:进的端

循环队列

  • 循环队列属于存储结构
  • 栈和队列都是线性表

计算

  • 公式:队尾-队头 (如果小于0则加上队列容量)
  • 通过队头指针队尾指针共同求得循环队列的元素
    • 队头指针:开始的位置
    • 队尾指针:结束的位置

题:某循环队列容量为50,队头指针为3,队尾指针为40,该队列的个数为()

由题意得:

  • 队尾-队头 = 40-3 = -10
  • ∵-10<0
  • ∴要加上队列容量:-10+50=40
  • 则该队列的个数为40


文章作者: Hui3c
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-ND 4.0 许可协议。转载请注明来源 Hui3c !
  目录