java - 甚至有 2^(n) - 1 的算法位于 Theta Ө(1) 中吗？

Question

所以我对我应该“发明”/“发现”的算法有疑问。这是一种计算 2^(n) - 1 为 Ө(n^n) 和 Ө(1) 和 Ө(n) 的算法。

我想了好几个小时，但我找不到两个任务的解决方案(第一个，最后一个是最简单的 imo，我在下面发布了算法)。但是我不够熟练，无法“发明”/“找到”一个非常慢和非常快的算法。

到目前为止我的算法是(在伪代码中):

为 Ө(n) 的那个

int f(int n) {

  int number = 2
  if(n = 0) then return 0 
  if(n==1)  then return 1 

  while(n > 1)
    number = number * 2
    n--

 number = number - 1
 return number

一个简单且有点明显的使用递归的方法，虽然我不知道它有多快(如果有人能告诉我那会很好):

int f(int n) {
  if(n==0) then return 0
  if(n==1) then return 1
  return 3*f(n-1) - 2*f(n-2)
}

Answer 1

1. 假设 n 不受任何常量限制(并且输出不应该是简单的 int，而是可以包含大整数的数据类型以允许它)- 那里是没有算法在 Ө(1) 中产生 2^n -1，因为输出本身的大小是Ө(log(n))，所以如果我们假设有这样的算法，让它在恒定时间内运行并进行小于 C 的操作，对于 n =
2^(C+1)，你只需要C+1操作来打印输出，这与 C 是上限的假设相矛盾，所以没有这样的算法。
2. 对于 Ө(n^n)，如果您有更高效的算法(例如 Ө(n))，您可以创建一个额外运行的无意义循环n^n 次迭代并且不做任何重要的事情，这将使您的算法 Ө(n^n)。
3. 还有一个Ө(log(n)*M(logn))算法，使用exponent by squaring ，然后简单地从这个值中减去 1。此处 M(x) 是包含 x 位数字的乘法运算符的复杂度。
4. 正如@kajacx 所说，您甚至可以通过应用 Fourier transform 来改进 (3)