数据结构&算法 算法基础



  • 算法基础

    算法是一个分步过程,它定义了一组指令,这些指令将以某种顺序执行以获得所需的输出。通常,算法是独立于基础语言而创建的,即,一种算法可以用一种以上的编程语言来实现。
    从数据结构的角度来看,以下是算法的一些重要类别-
    • 搜索 - 在数据结构中搜索项目的算法。
    • 排序 - 按特定顺序对项目进行排序的算法。
    • 插入 - 将项目插入数据结构的算法。
    • 更新 - 更新数据结构中现有项目的算法。
    • 删除 - 从数据结构中删除现有项目的算法。
  • 算法的特征

    并非所有过程都可以称为算法。算法应具有以下特征-
    • 明确 - 算法应清晰明确。它的每个步骤(或阶段)及其输入/输出都应该明确,并且结果只有一种含义。
    • 输入 - 算法应具有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
    
    
    在算法的设计和分析中,通常使用第二种方法来描述算法。分析人员可以轻松地忽略所有不需要的定义来分析算法。他可以观察正在使用哪些操作以及流程如何进行。编写步骤号是可选的。我们设计一种算法来解决给定问题。一个问题可以通过多种方式解决。
    dsa
    因此,对于给定的问题,可以得出许多解决方案算法。下一步是分析那些建议的解决方案算法并实施最合适的解决方案。
  • 算法分析

    假设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)随着输入大小的增加而线性增长。