数据结构与算法

算法基础

算法是一个循序渐进的过程,它定义了一组指令以一定的顺序执行以获得所需的输出。算法通常独立于底层语言创建,即一个算法可以用一种以上的编程语言实现。
从数据结构的角度来看,以下是一些重要的算法类别-
Search-在数据结构中搜索项目的算法。 Sort-以特定顺序对项目进行排序的算法。 Insert-在数据结构中插入项目的算法。 Update-更新数据结构中现有项目的算法。 Delete-从数据结构中删除现有项目的算法。

算法的特点

并不是所有的过程都可以称为算法。算法应具有以下特征-
Unambiguous-算法应该清晰明确。它的每个步骤(或阶段),以及它们的输入/输出都应该是清晰的,并且必须只导致一个含义。 Input-算法应该有 0 个或更多定义明确的输入。 Output-算法应该有 1 个或多个明确定义的输出,并且应该匹配所需的输出。 Finiteness-算法必须在有限步数后终止。 Feasibility-在可用资源的情况下应该是可行的。 Independent-算法应该有分步指导,应该独立于任何编程代码。

如何编写算法?

没有明确的算法编写标准。相反,它依赖于问题和资源。永远不会编写算法来支持特定的编程代码。
众所周知,所有编程语言都共享基本的代码结构,如循环(do、for、while)、流程控制(if-else)等。这些通用结构可用于编写算法。
我们以循序渐进的方式编写算法,但并非总是如此。算法编写是一个过程,是在明确问题域之后执行的。也就是说,我们应该知道我们正在为其设计解决方案的问题域。

示例

让我们尝试通过一个例子来学习算法写作。
问题-设计一个算法来添加两个数字并显示结果。
Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP
算法告诉程序员如何编写程序。或者,该算法可以写为-
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP
在算法的设计和分析中,通常使用第二种方法来描述算法。它使分析师可以轻松地分析算法而忽略所有不需要的定义。他可以观察正在使用哪些操作以及流程是如何进行的。
步骤编号,是可选的。
我们设计一种算法来获得给定问题的解决方案。一个问题可以通过多种方式解决。
一个问题很多解决方案
因此,对于给定的问题,可以推导出许多解决算法。下一步是分析那些提出的解决方案算法并实施最合适的解决方案。

算法分析

算法的效率可以在两个不同的阶段进行分析,即实施前和实施后。他们是以下-
先验分析-这是对算法的理论分析。衡量算法效率的方法是假设所有其他因素(例如处理器速度)保持不变并且对实施没有影响。 后验分析-这是对算法的经验分析。所选算法是使用编程语言实现的。然后在目标计算机机器上执行。在此分析中,会收集实际统计信息,例如所需的运行时间和空间。
我们将学习 先验算法分析。算法分析处理所涉及的各种操作的执行或运行时间。操作的运行时间可以定义为每次操作执行的计算机指令数。

算法复杂度

假设 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、现在,空间取决于给定变量和常量类型的数据类型,并将相应地相乘。

时间复杂度

算法的时间复杂度表示算法运行到完成所需的时间量。时间要求可以定义为一个数值函数 T(n),其中 T(n) 可以测量为步数,前提是每一步消耗恒定的时间。
例如,两个 n 位整数相加需要 n 个步骤。因此,总计算时间为 T(n) = c * n,其中 c 是添加两位所需的时间。在这里,我们观察到 T(n) 随着输入大小的增加呈线性增长。
昵称: 邮箱:
Copyright © 2022 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4