BCS*_*BCS 7 algorithm math complexity-theory
在常量工作空间中是否有办法进行任意大小和任意基本转换.也就是说,使用1对1映射n将范围内的数字序列转换为范围内[1,m]的ceiling(n*log(m)/log(p))数字序列[1,p](优选但不一定)保留lexigraphical顺序并给出顺序结果？
我对作为管道功能可行的解决方案特别感兴趣,ei能够处理比存储在RAM中更大的数据集.
我发现了许多解决方案,这些解决方案需要与输入大小成比例的"工作空间",但是没有一个可以通过恒定的"工作空间"来消除.
删除顺序约束会有什么不同吗？即:允许按字典顺序输入,以产生非按字典顺序排列的输出:
F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3)
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5)
一些想法:
这可能有用吗？
streamBase n - > convert(
n,lcm(n,p)) - > convert(lcm(n,p),p) - > streamBase p
(哪里lcm是最不常见的倍数)
在一般情况下,我认为这是不可能的.如果m是p(或反之亦然)的权力,或者如果它们都是共同基础的权力,则可以这样做,因为每组log m(p)都是独立的.但是,在一般情况下,假设您正在转换数字.基数的等价数字是a1 a2 a3 ... anp
sum(ai * mi-1for iin1..n)
如果我们已经处理了第一个i数字,那么我们就得到了i部分和.要计算i+1'部分和,我们需要添加.在一般情况下,这个数字在大多数地方都有非零数字,所以我们需要修改到目前为止我们处理过的所有数字.换句话说,在我们知道最终输出数字是什么之前,我们必须处理所有输入数字.ai+1 * mi
在特殊情况下,如果m是公共基数的幂,或者等价如果log m(p)是有理数,那么在前面附近的mi基数中只会有一些非零数字p,所以我们可以安全地输出我们的大部分数字到目前为止已计算好了.