计算机算法

来自站长百科
(重定向自算法
跳转至: 导航、​ 搜索
计算机算法

计算机算法,简称“算法”,代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序,求解一个给定的可计算或可解的问题,不同的人可以编写出不同的程序,来解决同一个问题。

算法是一组有穷的规则,它们规定了解决某一特定类型问题的一系列运算,是对解题方案的准确与完整的描述。制定一个算法,一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。

算法的特性[ ]

算法的特性包括:

  1. 确定性。算法的每一种运算必须有确定的意义,该种运算应执行何种动作应无二义性,目的明确;
  2. 能行性。要求算法中有待实现的运算都是基本的,每种运算至少在原理上能由人用纸和笔在有限的时间内完成;
  3. 输入。一个算法有0个或多个输入,在算法运算开始之前给出算法所需数据的初值,这些输入取自特定的对象集合;
  4. 输出。作为算法运算的结果,一个算法产生一个或多个输出,输出是同输入有某种特定关系的量;
  5. 有穷性。一个算法总是在执行了有穷步的运算后终止,即该算法是可达的。

满足前四个特性的一组规则不能称为算法,只能称为计算过程,操作系统是计算过程的一个例子,操作系统用来管理计算机资源,控制作业的运行,没有作业运行时,计算过程并不停止,而是处于等待状态。

算法的描述[ ]

算法的描述方法可以归纳为以下几种:

  1. 自然语言;
  2. 图形,如N-S图、流程图,图的描述与算法语言的描述对应;
  3. 算法语言,即计算机语言、程序设计语言、伪代码;
  4. 形式语言,用数学的方法,可以避免自然语言的二义性。

用各种算法描述方法所描述的同一算法,该算法的功用是一样的,允许在算法的描述和实现方法上有所不同。

算法的评价[ ]

一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

  • 算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。时间复杂度用“O(数量级)”来表示,称为“阶”。常见的时间复杂度有: O(1)常数阶;O(log2n)对数阶;O(n)线性阶;O(n2)平方阶。
  • 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。


相关条目[ ]


参考来源[ ]