简单的算法分析和优化 (1) 复杂度 为了描述一个算法的优劣,我们引入算法时间复杂度和空间复杂度的概念。 时间复杂度:一个算法主要运算的次数,用大O表示。通常表示时间复杂度时,我们只保留数量级最大的项,并忽略该项的系数。 例如某算法,赋值做了3n3+n2+8次,则认为它的时间复杂度为O(n3);另一算法的主要运算是比较,做 了4×2n+2n4+700次,则认为它的时间复杂度为O(2n)。 当然,如果有多个字母对算法的运行时间产生很大影响,就把它们都写进表达式。如对m×n 的数组遍历的时间复杂度可以写作O(mn)。 空间复杂度:一个算法主要占用的内存空间,也用大O表示。 在实际应用时,空间的占用是需要特别注意的问题。太大的数组经常是开不出来的,即使开出来了,遍历的时间消耗也是惊人的。 (2) 常用算法的时空复杂度 1s运算次数约为5,000,000 [1]。也就是说,如果把n代入复杂度的表达式,得数接近或大于5,000,000,那么会有超时的危险。 常见的数量级大小:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!) O(1)叫常数时间;O(n)、O(n2)、O(n3)、O(n4)……叫做多项式时间;O(2n)、O(3n)……叫做指数时间。 (3) 简单的优化方法 1. 时间的简单优化方法时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意: 整型运算耗时远低于实型运算耗时。 位运算速度极快。 逻辑运算比四则运算快。 +、-、*运算都比较快(-、*比+慢一点点,可以忽略不计)。 /运算比+、-、*慢得多(甚至慢几十倍)。 取余%和除法运算速度相当。 调用函数要比直接计算慢(因为要入栈和出栈)。 这些规律我们可以从宏观上把握。事实上,究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由编译器、系统决定。但是,少做运算(尤其在循环体、递归体中)一定能很大程度节省时间。 2. 空间的简单优化方法空间上的优化主要在于减小数组大小、降低数组维数等。常用的节省内存的方法有:压缩储存——见180页“A.7 状态压缩*”。 覆盖旧数据——例如滚动数组(见62页“(5) 使用滚动数组”)。 要注意的是,对空间的优化即使不改变复杂度,只是改变 n 的系数也是极有意义的。空间复杂度有时对时间也有影响,要想方设法进行优化。 3. 优化的原则 尽量不让程序做已做过的事。 不让程序做显然没有必要的事。 不要解决无用的子问题。 不要对结果进行无意义的引用。
[1] 不同资料给出的数值是不同的,不过这不要紧。在 NOIP中,只要你的算法正确,就不会在运行时间上“打擦边球”。
|