博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
分治法--二分查找、乘方、斐波那契数
阅读量:5104 次
发布时间:2019-06-13

本文共 3244 字,大约阅读时间需要 10 分钟。

1、二分查找

常见错误:

  • 死循环:循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.
  • 溢出:middle = left + (right - left) / 2
  • 终止条件:一般来说,如果左闭右闭,则left<=right; 如果一开一闭,则left<right; 关键看left能不能等于right,而且要考虑实际情况,有时不能这样简单终结,会出现死循环,如下面的binarySearch_better()。
running time analysis:T(n) = T(n/2) +   Θ(1)  ---> T(n) =  Θ(lgn)
 
正确算法:
1 //normal binarySearch without optimization, closed interval, return value is mid(maybe mid=left=right) 2 int binarySearch(int a[], int n, int k){ 3     if(n<1) return -1; 4  5     int left,right,mid; 6     left = 0;       //closed left 7     right = n-1;    //closed right 8  9     while( left<=right ){10         mid = left+(right-left)/2;11 12         if( a[mid]
k ) right = mid-1;14 else return mid;15 }16 return -1;17 }
View Code
减少比较次数为1次
//more efficient way, left closed right away interval, return value is mid=leftint binarySearch_better(int a[], int n, int k){    if( n<1 )   return -1;    int left,right, mid;    left = 0;   //closed left    right = n;  //open right    while( left+1!=right ){        mid = left+(right-left)/2;        if( a[mid]>k )  right = mid;        else left = mid;    }    if( a[left]!=k || left<0 )  return -1;    return left;} //find the location that k first showedint binarySearch_firstShow(int a[],int n, int k){    if( n<1 ) return -1;    int left,right,mid,last;    left=0;     //closed left    right=n-1;  //closed right    last=-1;    //record the first place k showed    while( left<=right ){        mid = left+(right-left)/2;        if( a[mid]>k )  right = mid-1;        else if( a[mid]
kint binarySearch_firstBig(int a[],int n, int k){ if( n<1 ) return -1; int left,right,mid,last; left=0; //closed left right=n-1; //closed right last=-1; //record the first place k showed while( left<=right ){ mid = left+(right-left)/2; if( a[mid]>k ){ right = mid-1; last = mid; } else left = mid+1; } return last;}
View Code

2、斐波那契数

running time analysis:
  • 采用递归,f(n) = f(n-1)+f(n-2),没有减少问题规模,反而扩大了,因为f(n-1)和f(n-2)的计算有重复的部分。
  • 从f1一个一个加过来计算,时间为Θ(n);
  • 缩减为非线性时间,采用规律:{f(n+1),f(n),f(n),f(n-1)} <==> a{1,1,1,0}^n,利用分治法,T(n) = T(n/2) + Θ(1) = Θ(lgn);
//{f(n+1),f(n),f(n),f(n-1)} <==> a{1,1,1,0}^n, return value is f(n)long long fibonacci( long long a[2][2],int n){    if(n==1){        a[0][0] = a[0][1] = a[1][0] = 1;        a[1][1] = 0;        return a[0][1];    }    long long b[2][2];    fibonacci(b,n/2);    for( int i=0; i<2; i++ )    for( int j=0; j<2; j++ ){        a[i][j] = 0;        for( int k=0; k<2; k++ )            a[i][j] += b[i][k]*b[k][j];    }    if( n%2==0 )    return a[0][1];    //n is odd, then a = a*{1,1,1,0};    int t1,t2;    t1 = a[0][0];    t2 = a[0][1];    a[0][0] = t1+t2;    a[0][1] = a[1][0] = t1;    a[1][1] = t2;    return a[0][1];}

 

3、乘方

running time analysis: T(n) = T(n/2) +  Θ(1) =  Θ(lgn)
//compute x^n.long long power(int x, int n){    if( n==1 )  return (long long)x;    long long half = power(x,n/2);    if( n/2*2 == n )   return half*half;    return half*half*x;}

 

  
posted on
2014-05-14 22:03 阅读(
...) 评论(
...)

转载于:https://www.cnblogs.com/hf-cherish/p/3728788.html

你可能感兴趣的文章
局域网内手机访问电脑网站注意几点
查看>>
IT项目经验和难点分享
查看>>
那些黑刘翔的人,你们的良心被狗吃了
查看>>
TreeMap和TreeSet在排序时如何比较元素?Collections工具类中的sort()方法如何比较元素?...
查看>>
Redis系列--内存淘汰机制(含单机版内存优化建议)
查看>>
最小二乘法
查看>>
iptables端口转发
查看>>
金融三问
查看>>
HTML5新API记录
查看>>
Android 8 AudioPolicy 分析
查看>>
Java Web开发后端常用技术汇总
查看>>
How to use jQuery countdown plugin
查看>>
富文本常用封装(NSAttributedString浅析)
查看>>
c++ STL
查看>>
json数据在前端(javascript)和后端(php)转换
查看>>
[Serializable]的应用--注册码的生成,加密和验证
查看>>
Groovy中那些神奇注解之ToString
查看>>
宇宙第一开发工具:vs2019 开发Python
查看>>
Tomcat Https配置
查看>>
待续--mysql中key 、primary key 、unique key 与index区别
查看>>