数据结构&算法算法基础

算法基础

算法是一个分步过程，它定义了一组指令，这些指令将以某种顺序执行以获得所需的输出。通常，算法是独立于基础语言而创建的，即，一种算法可以用一种以上的编程语言来实现。

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

搜索 - 在数据结构中搜索项目的算法。
排序 - 按特定顺序对项目进行排序的算法。
插入 - 将项目插入数据结构的算法。
更新 - 更新数据结构中现有项目的算法。
删除 - 从数据结构中删除现有项目的算法。

算法的特征

并非所有过程都可以称为算法。算法应具有以下特征-

明确 - 算法应清晰明确。它的每个步骤（或阶段）及其输入/输出都应该明确，并且结果只有一种含义。
输入 - 算法应具有0个或更多定义明确的输入。
输出 - 算法应具有1个或多个定义明确的输出，并且应匹配所需的输出。
有限性 - 算法必须在有限数量的步骤后终止。
可行性 - 用可用资源应该可行。
独立 - 算法应具有逐步指导，该逐步指导应独立于任何编程代码。

如何编写算法？

没有编写算法的明确定义的标准。而是取决于问题和资源。永远不会编写算法来支持特定的编程代码。众所周知，所有编程语言都共享基本的代码结构，例如循环（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)给出的运行时间和/或在以下方面由该算法所需的存储空间Ñ作为输入数据的大小。

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的存储空间量。算法所需的空间等于以下两个组成部分的总和-

固定部分，是存储某些数据和变量所需的空间，与问题的大小无关。例如，使用的简单变量和常量，程序大小等。
可变部分是变量所需的空间，其大小取决于问题的大小。例如，动态内存分配，递归堆栈空间等。

任何算法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)随着输入大小的增加而线性增长。