与二分分治有关的几个函数

来源：百度文库 编辑：神马文学网 时间：2024/04/30 09:27:08
与二分分治有关的几个函数     一、二进制1位计数
定义：n为一正整数，n的二进制表示中的位为1的个数记为γn；
[1,n)区间的数的二进制表示中的位为1的总数记为Ρn；
一般的，Pn=n*logn+O(n)，
若n=2^t，则：Pn=t*(2^(t-1))。
现在考虑如何快速计算Ρn。
1：递归解决方案
对Ρn，有递归：
_    _
Ρn=Ρ|_n/2_|+Ρ| n/2 |+|_n/2_|     (n>1,Ρ1=0)
于是，纯粹根据上面的递归计算Ρn，时间由下面的递归决定：
_     _
Tn=T|_n/2_|+T| n/2 |+1  (n>1,T1=0)
解之，得Tn=n-1。因此，时间复杂度是O(n)的，并且空间消耗也较大。
当然，可以有若干改进方法：
1：造一些基础数表。比如，对i<=64，预先计算出Pi，存入表中。以后递归到下标小于64的项时，可以
直接查表得解。
2：可以利用下面显然的一个递归关系：
Pn=P(n-1)+γ(n-1)         (n>1, P1=0)
于是，递归式变为：
Ρn=2*Ρ|_n/2_|+γ(|_n/2_|)+|_n/2_|     (n>1且n!=2^t，Ρ1=0)
Pn=t*n/2                                                 ( n=2^t )
于是，只需要有快速计算γn的算法就可以了。
计算γn的算法：
int  GetOnes( int n ){
int result=0;
do
n&=n-1, ++result;
while( n );
return n;
}
于是，复杂度就几乎为O(logn)了。
2：快速的对数阶解决方案
代码如下：
unsigned int   f ( unsigned int n ){
unsigned int  result=0, i, j=0;
for( i=31; i>=0; --i )
if( n & (1<result+=i*(1<<(i-1))+((1<return result+((j*(j-1))>>1);
}
复杂度为O(logn)。
二、末尾连续1计数
定义：n为一正整数，n的二进制表示中的末尾连续1的个数记为ψn；
[1,n)区间的数的二进制表示中的末尾连续1的总数记为Rn；
对一般的n，Rn=n+O(lbn) [lb()：以2为底的对数]，
若n=2^t，则：Rn=n-1。
同样，考虑如何快速计算Rn。
对Rn，有递归关系如下：
Rn=R(n-2^[_lbn_])+2^[_lbn_] -1      (n>1, R1=0)
于是，计算Rn亦有O(logn)的算法。
代码如下：
int      Rn( int n ){
if( n&(n-1)==0 )
return n-1;
int temp=1<return  Rn( n-temp )+temp-1;
}
三、应用
Pn与Rn在某些算法分析中，有很大作用。
如：
试分析：对二进制计数器，从1到n的自增运算中，一共发生多少次进位？
解：
一次n++运算发生的进位次数，与n的末尾连续1串的长度相等，即等于ψn。
于是 ，从1到n的自增运算中，一共发生Rn次进位。
除了在算法分析中有用之外，对二进制下的Pn与Rn分析与计算，对其他进制情况的分析及计算也是一个启发。
与二分分治有关的几个函数 与字符串数组有关的三个函数（Split函数、Join函数、Filter函数） 与老师有关的几个笑话 c# 日期有关的函数 c# 日期有关的函数 php的几个配置文件函数 几个常用的asp函数 几个简单的prototype函数 与“正确处理人民内部矛盾”有关的几个新提法 与“正确处理人民内部矛盾”有关的几个新提法k 有关ET的几个网站 几个ASP好用的自定义函数 printk函数的几个消息记录等级 宏函数与函数的比较 大一的二分之一 二分之一的智慧 大一的二分之一 尹中立：与万科有关的几个“意外”和“巧合”(南方周末 2007-7-26) 与“正确处理人民内部矛盾”有关的几个新提法 - 党政时评 - 七一社区论坛 有关于人际关系的几个分类！ 有关“地球运动”的几个误区 有关于人际关系的几个分类！ 有关于人际关系的几个分类 有关于人际关系的几个分类！999