(一)算法运行时间估计

估计某个算法的时间复杂度需要一些数学定义,如 T(N) = O(fn),表示T(N)的增长率小于等于fn; T(N) = Ω(fn),表示T(N)的增长率大于fn; T(N) = θ(fn),表示T(N)的增长率等于fn; T(N) = o(fn),表示T(N)的增长率小于fn. 我们一般考察O,即大O,时间上界.一个算法运行的时间进行估计,以便我们更好的了解程序设计与运行的优化方法.

估计法则1:

如果T1(N) = O(fn),t2(N) = O(gn),则有 T1(N)+T2(N) = max(O(fn),O(gn)) ,T1(N)*T2(N) = O(fn*gn)

估计法则2(循环):

一次循环的运行时间至多是循环体内语句运行时间乘以循环次数;嵌套循环为循环体内语句运行时间乘以各层循环次数之积.

估计法则3(顺序结构):

顺序结构运行时间等于各条语句运行时间之和.

估计法则4(分支结构):

分支结构运行时间不会大于分支中运行时间最长的那个分支体.

估计法则5(对数):

对数形式一般出现在一个算法用常数时间将问题大小削减一半(或者有形如k *= 2的形式), 如二分查找

综合以上法则,我们就可以分析出某个具体算法的时间上界

例:分析运行时间

1 Value = 0;
2    for( i= 1; i < N; i++)
4      for( j = 1;j < i*i; j++)
6          for( k = 0; k < j; k++)
8                    Value++;

Value++的运行时间为常数阶,第一层循环次数为N;第二层循环次数i*i与N²有关,因为i与N有关.同理第三层循环次数j与N² 有关.则N*N² *N²=N⁵,即O(N⁵)

(二)素数判断算法

在程序设计的学习过程中,判断一个数是否为素数的算法相信大家都非常熟悉了,这里与大家复习一下并提出更好的方案.

首先,什么是素数.素数就是除了1和它本身外,没有其他因数的正整数.啊,将n从2除到√n,这是我的,相信也是很多人的第一想法.那么有没有更好的方案呐?让我们从头开始.

尝试1:

1 bool isPrime(int n){
2 if(n <= 1)
3       return false;                              //1以及非正数不可能为素数,函数返回
4 for(int i = 2; i < n; i++){                  //从2开始找到n-1
5      if(n%i == 0)
6       return false;                   //被整除代表有其他因数,这不是素数,函数返回
7 }
8       return true;                               //检验完毕,为素数,函数返回
9 }

这是最原始的算法,根据素数定义.容易得到,最坏情况比较要进行n-2次,时间复杂度为O(n).对于判断一个大数的情况,显然费时.

尝试2:

1 bool isPrime(int n){
2  if(n <= 1)
3       return false;
4 for(int i = 2; i <= (n/2); i++){
5      if(n%i == 0)
6       return false;
7 }
8       return true;
9 }

因为一个数的因数总是成对出现(如2*3=6,2和3都是6的因数),且按这个数的中值对称分布,因此只需要算到这个数的一半就行了.显然,循环比较次数比尝试1少,但时间复杂度仍为O(n).

尝试3:

1 bool isPrime(int n){
2  if(n <= 1)
3      return false;
4 for(int i = 2; i <= sqrt(n); i++){
5    if(n%i == 0)
6      return false;
7 }
8      return true;
9 }

这个方法相信大家非常熟悉,也是最容易想到的.依据是若n有因数a和b,即n=a*b,那么必有一个因数位于2到√n之间,又因因数对称且成对出现,那么检验范围从2到√n就行了(我们当然可以检验√n到n-1),时间复杂度为O(√n)

尝试4:

 1 bool isPrime(int n){
 2  if(n == 2)                                 //2是偶数中唯一的素数
 3     return true;
 4  if(n <= 1 || n%2 == 0)           //除了2外,所有偶数都不是素数,至少有因数2
 5     return false;
 6 for(int i = 3; i <= sqrt(n); i+=2){
 7   if(n%i == 0)
 8     return false;
 9 }
10     return true;
11 }

注释说的很清楚了.这个算法比尝试3进一步减少了检验比较次数,时间复杂度为O(√n)

除了上面这些基本尝试(特别是尝试4,比较不错了)外,还有其他算法,如使用素数表的拉宾米勒测试等,还有些算法就需要很多的数学知识了,额.

书籍推荐:

谢谢大家!转载请注明出处,谢谢合作!