程序算法
对特定问题求解过程的描述
程序算法是对特定问题求解过程的描述,是指令的有限序列,每条指令完成一个或多个操作。通俗地讲,就是为解决某一特定问题而采取的具体有限的操作步骤。
程序算法特性
有穷性
在有限的操作步骤内完成。有穷性是算法的重要特性,任何一个问题的解决不论其采取什么样的算法,其终归是要把问题解决好。如果一种算法的执行时间是无限的,或在期望的时间内没有完成,那么这种算法就是无用和徒劳的,我们不能称其为算法。
确定性
每个步骤确定,步骤的结果确定。算法中的每一个步骤其目的应该是明确的,对问题的解决是有贡献的。如果采取了一系列步骤而问题没有得到彻底的解决,也就达不到目的,则该步骤是无意义的。
可行性
每个步骤有效执行,得到确定的结果。每一个具体步骤在通过计算机实现时应能够使计算机完成,如果这一步骤在计算机上无法实现,也就达不到预期的目的,那么这一步骤是不完善的和不正确的,是不可行的。
零个或多个输入
从外界获得信息。算法的过程可以无数据输入,也可以有多种类型的多个数据输入,需根据具体的问题加以分析。
一个或多个输出
算法得到的结果就是算法的输出(不一定就是打印输出)。算法的目的是为解决一个具体问题,一旦问题得以解决,就说明采取的算法是正确的,而结果的输出正是验证这一目的的最好方式。
算法复杂度
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度空间复杂度来考虑。
时间复杂度
算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做T(n)=Ο(f(n));因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。
空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
最新修订时间:2023-12-23 15:57
目录
概述
程序算法特性
参考资料