Существует ли даже алгоритм для 2^(n) - 1, который лежит в Theta Ө (1)?

Question

поэтому у меня есть вопрос об алгоритме, который я должен «изобрести»/«найти». Это алгоритм, который вычисляет 2^(n) - 1 для Ө (n^n) и Ө (1) и Ө (n).

Я думал несколько часов, но не смог найти решения для обеих задач (первые, в то время как последний был easist imo, я разместил алгоритм ниже). Но я недостаточно квалифицирован, чтобы «изобретать»/«находить» один для очень медленного и очень быстрого алгоритма.

До сих пор мои алгоритмы (в псевдокод):

Один для Ө (п)

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

что-то вроде:

HugeInt h = 1; 

h = h << n; 
h = h - 1; 

Очевидно, что HugeInt является псевдокодом для целочисленного типа, который может быть произвольного размера, что позволяет использовать любые n.

=====

Посмотрите на ответ Amit вместо!

Answer 2

1. Предполагая n не ограничена какой-либо постоянной (и выход не должен быть простым int, но тип данных, которые могут содержать большие целые числа, чтобы позволить его) - нет алгоритма с получением 2^n -1 в Ө(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, вы можете даже улучшить (3) путем применения Fourier transform

Answer 3

в Ө (п^п) слишком сложно для меня, но реальный Ө (1) алгоритм на любой «двоичный "архитектура будет:

return n-1 bits filled with 1 

(при условии, ваша архитектура может выделить и заполнить п-1 бит в постоянная время) ;)