每一条指令表示一个或多个操作。算法可以有三种表示形式:
?伪代码
?自然语言
?流程图
算法和程序是两个不同的概念。
一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味
着不是所有的计算机程序都是算法。
2、算法分析
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方
法通常是事前分析:求出该算法的一个时间界限函数。
与此相关的因素有:
依据算法选用何种策略;
问题的规模;
程序设计的语言;
编译程序所产生的机器代码的质量;
机器执行指令的速度;
数据的初试状态有关
撇开软硬件等有关部门因素,可以认为一个特定算法“运行工作量”的大小,只依赖
于问题的规模(通常用n表示),表示成是问题规模的函数。
3、时间复杂度
算法中基本操作重复执行的次数是问题规模n的某个函数,其时间量度记作
t(n)=o(f(n)),称作算法的渐近时间复杂度(Asyptotictiplexity),简称时间复杂度。
一般地,常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来
表示。
定理:若A(n)=an+a-1n-1+…+a1n+a0是一个次多项式,
则A(n)=o(n)
表示时间复杂度的阶有:
o(1):常量时间阶o(n):线性时间阶
o(㏒n):对数时间阶o(n㏒n):线性对数时间阶
o(nk):k≥2,k次方时间阶
其关系为: