2021-11-15 数据结构与算法简介

wuchangjian2021-11-15 15:55:17编程学习

数据结构与算法简介,Leetcode入门及攻略

  • 1. 数据结构与算法
    • 1.1 相关定义
    • 1.2 为什么要学习算法和数据结构
    • 1.3 数据结构
      • 1.3.1 数据的逻辑结构
      • 1.3.2 数据的物理结构
    • 1.4 算法
      • 1.4.1 算法的基本特性
      • 1.4.2 算法追求的目标
  • 2. 算法复杂度
    • 2.1 时间复杂度
      • 2.1.1 渐进符号
      • 2.1.2 时间复杂度的计算
      • 2.1.3 最佳, 最坏,平均时间复杂度
    • 2.2 空间复杂度

1. 数据结构与算法

数据结构是程序的骨架,而算法则是程序的灵魂
在这里插入图片描述

1.1 相关定义

  1. 算法(Algorithm): 解决问题的方法或过程
  2. 数据结构(Data Structure): 数据的计算机表示和相应的一组操作
  3. 程序(Program): 算法和数据结构的具体实现

以做菜举例: 把程序设计比作做菜,那么数据结构就是食材和调料,算法则是不同的烹饪方式,有着不同的组合

1.2 为什么要学习算法和数据结构

在程序设计中,对于待解决的问题,我们追求的是:选择更合适的数据结构,使用花费时间更少,占用空间更小的算法

1.3 数据结构

数据结构(Data Structure): 数据的组织结构,用来组织, 存储数据

  1. 研究内容:数据结构研究的是数据的逻辑结构,物理结构以及它们之间的相互关系,并对这种结构定义相应的运算,设计出相应的算法,并确保经过这些运算之后所得到的数据结构仍保持原来的数据类型
  2. 作用:提高计算机硬件的利用率

1.3.1 数据的逻辑结构

逻辑结构(Logical Structure):数据元素之间的相互关系

  1. 集合结构:数据元素同属于一个集合,除此之外无其他关系
  2. 线性结构:数据元素之间是一对一的关系
  3. 树形结构:数据元素之间是一对多的层次关系
  4. 图形结构:数据元素之间是多对多的关系

1.3.2 数据的物理结构

物理结构(Physical Structure):数据的逻辑结构在计算机中的存储方式

  1. 顺序存储结构(Sequential Storage Structure):将数据元素存放在一片地址连续的存储单元里,数据元素之间的逻辑关系通过数据元素的存储地址来直接反映在这里插入图片描述
    **注意:在顺序存储结构中,逻辑上相邻的数据元素在物理地址上也必然相邻 **
    • 优点:简单, 易理解,实际上占用最少的存储空间
    • 需要占用一片地址连续的存储单元;存储分配要事先进行;对于一些操作的时间效率较低
  2. 链式存储结构(Linked Storage Structure):将数据元素存放在任意的存储单元里,存储单元可不连续在这里插入图片描述
    注意:链式存储需要指针
    • 优点:存储空间不必事先分配,在需要存储空间的时候可以临时申请,不会造成空间的浪费;一些操作的时间效率远比顺序存储结构高
    • 缺点:不仅数据元素本身的数据信息要占用存储空间,指针也需要占用存储空间,链式存储结构比顺序存储结构的空间开销大。

1.4 算法

算法(Algorithm):解决特定问题求解步骤的准确而完整的描述,在计算机中表现为一系列指令的集合,算法代表着用系统的方法描述解决问题的策略机制
算法,就是指解决问题的方法

1.4.1 算法的基本特性

  1. 输入:对于待解决的问题,都要以某种方式交给对应的算法。在算法开始之前最初赋给算法的参数称为输入。
  2. 输出:算法是为了解决问题存在的,最终总需要返回一个结果。所以至少需要一个或多个参数作为算法的输出。
  3. 有穷性:算法必须在有限的步骤内结束,并且应该在一个可接受的时间内完成。
  4. 确定性:组成算法的每一条指令必须有着清晰明确的含义,不能令读者在理解时产生二义性或者多义性。就是说,算法的每一个步骤都必须准确定义而无歧义。
  5. 可行性:算法的每一步操作必须具有可执行性,在当前环境条件下可以通过有限次运算实现。也就是说,每一步都能通过执行有限次数完成,并且可以转换为程序在计算机上运行并得到正确的结果。

1.4.2 算法追求的目标

总体目标

  1. 所需运行时间更少 (时间复杂度更低)
  2. 占用内存空间更小 (空间复杂度更低)

但在实际中,兼顾时间复杂度和空间复杂度的算法是不存在的,这时我们需要结合自己具体的情况,采取以空间换时间或者以时间换空间的策略
但一个好的算法还应该追求以下目标:

  1. 正确性:算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期的需求。
  2. 可读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当,方便自己和他人阅读,便于后期修改和调试
  3. 健壮性: 算法对非法数据以及操作有较好的反应和处理

2. 算法复杂度

算法复杂度(Algorithm complexity): 在问题的输入规模为 n 的条件下,程序的时间使用情况和空间使用情况
比较算法优劣的两种方法:

  1. 事后统计:将两个算法各编写一个可执行程序,交给计算机执行,记录下各自的运行时间和占用存储空间的实际大小,从中挑选出最好的算法
  2. 预先估算:在在算法设计出来之后,根据算法中包含的步骤,估算出算法的运行时间和占用空间。比较两个算法的估算值,从中挑选出最好的算法

一般选择第二种方式,第一种方式的工作量太大
在第二种方式下, 我们只关心随着问题规模 n 扩大时,时间开销、空间开销的增长情况。
问题规模n:算法问题输入的数据量大小.对于不同的算法,定义也不相同

  • 排序算法中:n 表示需要排序的元素数量。
  • 查找算法中:n 表示查找范围内的元素总数:比如数组大小、二维矩阵大小、字符串长度、二叉树节点数、图的节点数、图的边界点等。
  • 二进制计算相关算法中:n 表示二进制的展开宽度。

2.1 时间复杂度

时间复杂度(Time Complexity):在问题的输入规模为n的情况下,算法运行所需要花费的时间,可以记作T(n)

度量标准:基本操作次数
基本操作:算法执行中的每一条语句
在这里插入图片描述

2.1.1 渐进符号

渐进符号实际上是专门用来刻画函数的增长速度的。
只保留最高次幂(在问题规模很大时,其余部分并不会造成太大影响)
最常用的为下面这种
在这里插入图片描述

2.1.2 时间复杂度的计算

  1. 找出算法中的基本操作(基本语句):算法中执行次数最多的语句就是基本语句,通常是最内层循环的循环体部分。
  2. 计算基本语句执行次数的数量级:只需要计算基本语句执行次数的数量级,即保证函数中的最高次幂正确即可。
  3. 用大O表示法表示时间复杂度:将上一步中计算的数量级放入 O 渐进上界符号中。
  • 加法原则:总的时间复杂度等于量级最大的基本语句的时间复杂度
  • 乘法原则:循环嵌套代码的复杂度等于嵌套内外基本语句的时间复杂度的乘积

2.1.3 最佳, 最坏,平均时间复杂度

  • 最佳时间复杂度:每个输入规模下用时最短的输入对应的时间复杂度
  • 最坏时间复杂度:每个输入规模下用时最长的输入对应的时间复杂度
  • 平均时间复杂度:每个输入规模下所有可能输入对应用时平均值的复杂度(随机输入下期望用时的复杂度)。

2.2 空间复杂度

空间复杂度(Space Complexity):在问题的输入规模为n的条件下,算法所占用的空间大小,可以记作为 S(n)。一般将算法的辅助空间 作为衡量空间复杂度的标准
空间复杂度与时间复杂度有许多共通之处,就不再过多赘述.
算法所需空间主要有两个方面:

  1. 局部变量(算法范围内定义的变量)所占用的存储空间
  2. 系统为实现递归(如果算法是递归的话)所使用的堆栈空间

链接: DataWhale算法通关手册.

相关文章

2021-11-18~19 Re 逆向工程略览 三 IDA Pro使用【T.O.CTF】

逆向工程最基本的方法是静态分析,而IDA Pro,也就是...

Problem J: IP地址

错误:字符串减去48          用完初始化  这个题好麻烦啊...

基本数据类型之间的运算规则:

前提这里讨论只是7种基本数据类型变量间的运算。不包含boolean类型的。 1.自动类...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。