算法时间复杂度的定义:(推荐学习:php视频教程)
在进行算法分析时,语句总的执行次数t(n)是关于问题规模n的函数,进而分析t(n)随n的变化情况并确定t(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:t(n)= o(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用大写o()来体现算法时间复杂度的记法,我们称之为大o记法。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为o(1),另外,在时间频度不相同时,时间复杂度有可能相同,如t(n)=n^2+3n+4与t(n)=4n^2+2n+1它们的频度不同,但时间复杂度相同,都为o(n^2)。
按数量级递增排列,常见的时间复杂度有:
常数阶o(1),对数阶o(log2n)(以2为底n的对数,下同),线性阶o(n),
线性对数阶o(nlog2n),平方阶o(n^2),立方阶o(n^3),...,
k次方阶o(n^k),指数阶o(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
算法空间复杂度
与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。
记作:
s(n)=o(f(n))
算法执行期间所需要的存储空间包括3个部分:
算法程序所占的空间;
输入的初始数据所占的存储空间;
算法执行过程中所需要的额外空间。
在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术。
更多php相关技术文章,请访问php图文教程栏目进行学习
以上就是算法的时间复杂度和空间复杂度的详细内容。
