数据结构 - 算法基础

算法是一个逐步的过程,它定义了一组指令,这些指令按特定顺序执行以获得所需的输出.算法通常独立于底层语言创建,即算法可以用多种编程语言实现.

从数据结构的角度来看,以下是算法的一些重要类别 :

  • 搜索 : 搜索数据结构中的项目的算法.

  • 排序 : 按特定顺序对项目进行排序的算法.

  • 插入 : 在数据结构中插入项目的算法.

  • 更新 : 用于更新数据结构中现有项目的算法.

  • 删除 : 从数据结构中删除现有项目的算法.

算法的特征

不所有程序都可以称为算法.算法应具有以下特征 :

  • 明确 : 算法应清晰明确.它的每个步骤(或阶段)及其输入/输出应该是明确的,并且必须只有一个含义.

  • 输入 : 算法应具有0个或更多明确定义的输入.

  • 输出 : 算法应该有一个或多个明确定义的输出,并且应该与所需的输出匹配.

  • 有限性 : 算法必须在有限步骤后终止.

  • 可行性 : 使用可用资源应该是可行的.

  • 独立 : 算法应该有逐步的方向,它应该独立于任何编程代码.

如何编写算法?

编写算法没有明确定义的标准.相反,它取决于问题和资源.永远不会编写算法来支持特定的编程代码.

我们知道所有编程语言共享基本代码结构,如循环(do,for,while),流控制(if-else)这些常见结构可用于编写算法.

我们逐步编写算法,但情况并非总是如此.算法编写是一个过程,在问题域定义明确后执行.也就是说,我们应该知道我们正在设计解决方案的问题域.

示例

让我们尝试通过使用来学习算法编写一个例子.

问题 : 设计一个算法来添加两个数字并显示结果.

 步骤1 : START 
 第2步 : 声明三个整数 a,b 和 c  
 第3步 : 定义a和b  
 第4步 : 添加a和b的值
 第5步 : 将步骤4的输出存储到c  
 步骤6 : 打印c  
 第7步 : STOP

算法告诉程序员如何编写程序代码.或者,算法可写为 :

 步骤1 : 开始添加
 第2步 : 得到 a和b的值  
 第3步 : c = a+b 
 第4步 : 显示c 
 第5步 : STOP

在算法的设计和分析中,通常使用第二种方法来描述算法.它使分析人员可以轻松分析算法,忽略所有不需要的定义.他可以观察正在使用的操作以及流程如何流动.

步数是可选的.

我们设计了一种算法来获得给定问题的解决方案.一个问题可以通过多种方式解决.

一个问题很多解决方案

因此,可以针对给定问题导出许多解算法.下一步是分析那些提出的解决方案算法并实施最合适的解决方案.

算法分析

算法的效率可以分析为两个不同阶段,实施前和实施后.它们是以下 :

  • 先验分析 ;这是对算法的理论分析.算法的效率是通过假设所有其他因素(例如处理器速度)是恒定的并且对实现没有影响来测量的.

  • 后验分析 : 这是对算法的实证分析.所选算法使用编程语言实现.然后在目标计算机上执行此操作.在此分析中,收集了所需的运行时间和空间等实际统计数据.

我们将了解 a priori 算法分析.算法分析处理所涉及的各种操作的执行或运行时间.操作的运行时间可以定义为每次操作执行的计算机指令数.

算法复杂度

假设 X 是一种算法, n 是输入数据的大小,算法X使用的时间和空间是决定X效率的两个主要因素.

  • 时间因素 : 时间是通过计算关键操作的数量来衡量的,例如排序算法中的比较.

  • 空间因子 : 通过计算算法所需的最大内存空间来测量空间.

算法的复杂性 f(n) n 的形式给出算法所需的运行时间和/或存储空间作为输入数据的大小.

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的内存空间量.算法所需的空间等于以下两个组件的总和 :

  • 一个固定的部分是一个存储某些数据和变量所需的空间,与问题的大小无关.例如,使用的简单变量和常量,程序大小等.

  • 变量部分是变量所需的空间,其大小取决于变量的大小.问题.例如,动态内存分配,递归堆栈空间等.

任何算法P的空间复杂度S(P)为S(P )= C +  SP(I),其中C是固定部分,S(I)是算法的可变部分,它取决于实例特征I.下面是一个简单的例子,试图解释概念 :

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C=A+B+10
Step 3 -  Stop

这里我们有三个变量A,B和C以及一个常量.因此S(P)= 1 +  3.现在,空间依赖于给定变量和常量类型的数据类型,并且它将相应地相乘.

时间复杂度

时间复杂度algorithm表示算法运行完成所需的时间量.时间要求可以定义为数值函数T(n),其中T(n)可以作为步数来测量,只要每个步骤消耗恒定的时间.

例如,加法两个n位整数的步骤采用 n 步骤.因此,总计算时间为T(n)= c∗ n,其中c是加两位的时间.在这里,我们观察到T(n)随着输入大小的增加而线性增长.