java - 生成代表最小 pow() 结果的一系列数字

Question

假设 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) 的解决方案，这只是我的直觉，可能存在..

Answer 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()