算法基础

算法说简单些就是求解过程,它为获得所需结果而定义了一组按顺序执行的指令。算法通常独立于底层语言,即一个算法可以使用多种编程语言实现。

从数据结构的角度看,算法主要分为以下几类:

  • 搜索——从一数据结构结构中找出特定项。
  • 排序——将一组数据按制定顺序排序
  • 插入——向数据结构中插入一项
  • 更新——更新数据结构中的某一项
  • 删除——删除数据结构中某一项

算法的特征

并非所有过程都能称为算法,算法必须具有以下几个特征:

  • 明确性——算法应当清楚明确,它的每个步骤,输入输出,都只能指向一个含义。
  • 输入——算法应当有0个或多个输入。
  • 输出——算法必须有1个过多个输出并与预定结果相匹配。
  • 有穷性——算法必须在有限个步骤后终止。
  • 可行性——对于可利用的资源是可行的。
  • 独立性——算法的步骤应当独立于代码。

如何编写一个算法

如何编写算法并没有一个标准,它依赖于特定的问题和所给的资源,算法也从不会只为一种编程语言服务。

我们知道所有的编程语言都提供了基本的结构比如循环(do,for,while),流程控制 (if-else)等。这些常见的结构就可以用来写算法。编写算法必须明确问题的范围,然后设计解决方案。

举例

编写一个算法计算两数之和并显示结果。

  • step 1− 开始
  • step 2− 声明三个变量a、b、c
  • step 3− 确定a、b的值
  • step 4− 计算a+b
  • step 5− 将step 4的结果存储到c中
  • step 6− 打印c
  • step 7− 结束

算法告诉程序员如何编写程序,也可以写为:

  • step 1− 开始相加
  • step 2− 获取a、b的值
  • step 3− c ← a + b
  • step 4− 打印 c
  • step 5− 结束

在设计和分析算法时,通常使用第二种方法。这样分析时能够忽略不必要的定义,把注意力放在使用的操作和流程的控制上。

一个问题通常有多种解决方案。算法

这些方案都是可行的,所以下一步是分析哪一种是最优的。

算法分析

分析一个算法的效率通常有两种方法。

  • 理论分析——假定所有其他因素比如处理器速度都是恒定的,且对算法的实施无影响。
  • 实证分析——使用一种编程语言实现算法,并在计算机上运行,收集运行所需的时间与空间。

这里我们使用实证分析,算法的分析涉及各种操作的执行或运行时间,而运行时间又可以定义为操作执行的计算机指令数目。

算法复杂度

假设X是一个算法,n是输入数据的大小,算法所使用的时间和空间是衡量其效率的重要因素。

  • 时间因素——取决于关键步骤的执行次数,比如排序操作中的比较次数。
  • 空间因素——取决于算法所需的最大内存。

算法复杂度f(n)给出了输入为n的情况下算法的运行时间和所需存储空间。

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的内存空间,通常有两部分组成1、固定部分用于存储一定的数据和变量,这部分是独立于问题之外的。比如使用的变量和常量。(C)

2、变化部分是变量所需空间,取决于问题的大小,比如动态内存分配、递归堆栈空间等。SP(I)

空间复杂度S(P)=C+SP(I)。可用下面这个例子简单解释这个概念:

  • Algorithm: SUM(A, B)
  • Step 1 – START
  • Step 2 – C ← A + B + 10
  • Step 3 – Stop

这里我们有三个变量和一个常量,因此S(P) = 1+3,现在所需空间取决于变量类型与常量类型。

时间复杂度

时间复杂度表示算法运行所需时间,可定义为一个数值函数T(n),在已知每一步所需时间的情况下,可以用步骤数衡量。

例如,两个n位整数相加需要N步。因此,总的计算时间T(n)= C * N,C是两位相加所需时间,T(n)随输入数据的增大呈线性增长。

转载请参看关于博客页面相关要求。