- 如果
b
足够小,那么使用 sqrt
表的复杂度为 O(1)
- 如果不是,则使用位近似的复杂度为
O(b/2) = O(log n)
- 使用完美平方表的复杂度也是
O(b/2) = O(log n)
但是通过更快的操作(只需比较和位运算),b
位数可以是最大 b/2
位数的完全平方数,因此表格具有 2^(b/2)
个条目,其中每个条目都是 b
位数,并且近似索引搜索(类似于二进制搜索)需要 b/2
步
- 可以通过近似改进一些内容
创建近似函数
y=approx_sqrt(x);
并计算
y
,现在您只需检查来自
< y-c , y+c >
的值
其运行时间为~T(2c)
,其中
c
是与近似精度
(1,2,3,...)
有关的常数。大多数近似在较大的值上都会出错,因此您可以使
c=log(b)
,您的
复杂度突然变为O(log b) = O(log log n)
,这正是您正在寻找的东西。
以下是我测试过的实现:
int is_square(int x,int &cnt)
{
int y,yy;
for (y=x,yy=x;yy;y>>=1,yy>>=2);
if (y) y=(y+(x/y))>>1;
if (y) y=(y+(x/y))>>1;
if (y) y=(y+(x/y))>>1;
cnt=1;
yy=y*y; if (yy==x) return y;
if (yy<x) for (;;)
{
cnt++;
y++;
yy=y*y;
if (yy==x) return y;
if (yy> x) return 0;
}
else for (;;)
{
cnt++;
y--;
yy=y*y;
if (yy==x) return y;
if (yy< x) return 0;
}
}
我为您添加了cnt,这样您就可以自己测试复杂性。我的使用的近似需要一个良好的起始值,因此我使用了减半位数,显然是O(log b)
,但对于和float
值,指数/位数已知,因此只需转换为单个位/字/基数/指数移位O(1)
。顺便说一句,这就是大多数sqrt
或log
函数的近似所做的IEEE浮点魔术。
我的测量结果比我最初的估计更好(即使是非精确的巴比伦近似):
/*----------------
| N | T |
------------------
| 1000000000 | 6 |
| 100000000 | 4 |
| 10000000 | 2 |
| 1000000 | 2 |
----------------*/
其中N
是循环N
,用于测试。 T
是在不同的近似值(更适合您的需求)下测试数字< 0,N>
的最大cnt
值,可以在这里查看。
所以我的答案是是的,存在比O(log n)
更快的算法来确定n
是否为完全平方数(例如上面的算法也计算了sqrt
),但如果您还要计算基本函数的复杂度,那么恐怕答案是否,因为即使是位运算在大数上也是O(log n)
!
顺便说一句,二分查找sqrt
也可以不使用乘法。