在码农港湾
做一个实实在在的内行人

数据结构算法基础

算法是一步步的过程,它定义一组指令在一定的顺序,以执行获得所需的输出。算法通常在独立的基本语言,即一种算法可以在一个以上的程序设计语言中实现。

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

  • 搜索 − 在一个数据结构中搜索一个项目算法。
  • 排序− 排序在某些顺序算法
  • 插入 − 在数据结构中插入项算法
  • 更新 − 在数据结构中更新现有的项算法
  • 删除 − 从数据结构中删除现有项目算法

算法的特点

并非所有的程序可以被称为一种算法。算法应具有下面特征 –

  • 明确 − 算法应该是明确的,毫不含糊的。它的每个步骤(或相),和它们的输入/输出的应明确和必须导致只有一个意思
  • 输入 − 算法应该具有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

在设计和算法分析,通常第二个方法是,用于描述的算法。它可以很容易的分析算法忽略所有不必要的定义。可以观察正在使用什么操作方法以及该过程是流动的。

写入步骤的数字是可选的。

我们设计一个算法,获得特定问题的解决方案。问题可以有一个以上的方式解决。

one problem many solutions

因此,许多解决方案的算法可以衍生为一个给定的问题。下一步就是分析这些提议解决方案的算法和实现最适合的。

算法分析

算法的效率可以在两个不同的阶段进行分析,实施前和实施后,如下所述 −

  • 先验分析 − 这是一种算法的理论分析。算法的效率是通过假设所有其它因素,例如测量,处理器速度,是常数,对实施无影响。
  • 后验分析 − 这是一种算法的实证分析。所选的算法使用编程语言来实现。这接着目标计算机的机器上执行。在这种分析中,实际统计像运行时间和所需的空间,会被收集。

我们将在这里学习的先验算法分析。算法分析与处理涉及的各种操作的执行或运行时间。操作的运行时间可以定义为每操作来执行的计算机指令编号。

算法复杂度

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


码农刷题必备工具 VS 码农进阶必读书籍

IT面试宝典宝典書城