3

假设next()是生成这个系列的函数：

 8
 9
 16
 25
 27
 32
 36
 49
 64
 81

哪个是 

i=2,3,....
j=2,3,....
f(n) =   minimum( pow(i,j) )   &&   f(n) > f(n-1)

我可以想出这个 O(n) 代码。是否有 O(1) 或 O(lg n) 解决方案？

    int m =2, n = 2;
    int last =4;

   void next() {
      int a=m+1,b=n+1;
      long t = pow(a,b);
      int ma = max(m,n);
      //cout<<" max = "<<ma<<endl;
      for(int i=2;i<=ma+1;++i){
         for(int j=2;j<=ma+1;++j){
            if(pow(i,j) > last && pow(i,j) <= t) {
             a=i,b=j;
             t = pow(i,j); 
            }
         }
      } 
      if(a>m) m=a;
      if(b>n) n=b;
      last = t;
      //cout<<"\t"<<a<<"\t"<<b<<"\t"<<pow(a,b)<<endl;
      cout<<" \t"<<pow(a,b)<<endl;
     return;
    }
}

注意： 1. 当我提到复杂性时，我只是在谈论对 next() 的一次调用。2. 缓存当然会有所帮助，但是我们可以考虑 lg-n 空间进行缓存吗？哎呀，缓存一切都更快。:) 3. 我不知道常数空间复杂度是否存在 O(lg-n) 的解决方案，这只是我的预感，可能存在..

4

3 回答 3

1

示例 python 代码，显然并不完美，但确实展示了如何进行惰性迭代。内存使用量为 O（服务的项目数），时间乘以它的对数。

import heapq

def power_seq(min_b, min_p):
    heap = []
    in_heap_table = {}
    cur_b, cur_p = min_b, min_p 
    heapq.heappush(heap, (power_value(cur_b, cur_p), cur_b, cur_p))
    in_heap_table[power_value(cur_b, cur_p)] = True
    while True:
        power, cur_b, cur_p = heapq.heappop(heap)
        yield power,cur_b, cur_p
        new_b = cur_b + 1
        new_p = cur_p + 1

        if power_value(new_b, cur_p) not in in_heap_table:
            heapq.heappush(heap, (power_value(new_b, cur_p), new_b, cur_p))
            in_heap_table[power_value(new_b, cur_p)] = True

        if power_value(cur_b, new_p) not in in_heap_table:
            heapq.heappush(heap, (power_value(cur_b, new_p), cur_b, new_p))
            in_heap_table[power_value(cur_b, new_p)] = True



# Can be made O(log p) if we want.
def power_value(b,p):
    power = 1
    while p >= 1:
        power = power*b
        p = p-1
    return power



def main():
    count = 0
    for tup in power_seq(2,2):
        print tup
        count += 1
        if count > 30:
            break

if __name__ == "__main__":
    main()
于 2013-03-13T21:55:12.353 回答
0

我为此设想的方法是通过生成器对所有功率结果的排序列表进行某种惰性构造。

想象一个无穷无尽的 x^y 结果场——x 在一个方向，y 在另一个方向。现在想象一条从 2^2（为简单起见，我们称其为 1）的路径，一个向东到 3^2，一个西南到 2^3，一个向南到 2^4，两个东北，一个向东，西南三次，一次向南……等等，斜着锯齿形地向外移动。

当你在所有 x^ys 上通过这个 zig-zag 路径时，将它们添加到一个自动排序的集合中，总共是 O(nlogn)。但是，我们很懒，想尽快停下来。

当你被问到第 n 大功率时，做锯齿形并建立集合，跟踪每个锯齿形产生的最低值是多少。如果最小值大于当前列表中第 n 位以下列表中的所有值，我们知道我们永远不会在列表中插入一个较小的数字，这会改变我们返回的结果 - 所以我们返回它。

此外，如果要求您提供第 n 个最大功率，您可以立即检查最小值是否足够低以更改该值，如果不是则立即返回。

该算法不是最理想的，因为功率在一个方向上的增长速度比在另一个方向上的增长速度更快 - 因此，一条偏向于在较慢的增长方向上覆盖比在较快的增长方向上更多的值的路径将需要搜索更少的值来返回第 n 个最大的功率。

于 2013-03-13T22:55:35.463 回答
0

（我不知道你是否知道你的问题是关于完美数字系列的）

一种可能更快的蛮力算法：在给定范围内生成所有可能的完美幂，并将它们插入到排序列表中。但是，我不知道您必须期望有多少重复项。绝对需要比您的方法更多的内存，但您没有给出任何限制:)

于 2013-03-13T10:15:02.533 回答