Да, ваша проницательность верна. Это называется динамическим программированием . Это обычно общий компромисс времени выполнения памяти.

В случае с fibo вам даже не нужно кэшировать все данные :

[редактировать] Автор вопроса, похоже, ищет общий метод кэширования, а не метод вычисления Фибоначчи. Поищите в Википедии или посмотрите на код другого плаката, чтобы получить этот ответ. Эти ответы линейны по времени и памяти.

**Here-это линейно-временной алгоритм O (n), постоянный в памяти **

in OCaml:

let rec fibo n = 
    let rec aux = fun
        | 0 -> (1,1)
        | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
    let (cur,prec) = aux n in prec;;



in C++:

int fibo(int n) {
    if (n == 0 ) return 1;
    if (n == 1 ) return 1;
    int p = fibo(0);
    int c = fibo(1);
    int buff = 0;
    for (int i=1; i < n; ++i) {
      buff = c;
      c = p+c;
      p = buff;
    };
    return c;
};

Это происходит в линейном времени. Но Лог на самом деле возможен !!! Программа ру тоже линейна, но гораздо медленнее, и использует память.

Вот лог-алгоритм O(log(n))

Теперь для алгоритма log-time (путь намного быстрее), Вот метод : Если вы знаете u (n), u (n-1), вычисление u (n+1), u (n) может быть выполнено путем применения матрицы:

| u(n+1) |  = | 1 1 | | u(n)   |
| u(n)   |    | 1 0 | | u(n-1) |    

Так что у вас есть :

| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |

Вычисление экспоненты матрицы имеет логарифмическую сложность. Просто реализуйте рекурсивно эту идею :

M^(0)    = Id
M^(2p+1) = (M^2p) * M
M^(2p)   = (M^p) * (M^p)  // of course don't compute M^p twice here.

Вы также можете просто диагонализировать его (не сложно), вы найдете золотое число и его сопряженность в собственном значении, и результат даст вам математическую формулу EXACT для u(n). Он содержит степени этих собственных значений, так что сложность все равно будет логарифмической.

Fibo часто используется в качестве примера для иллюстрации динамического программирования, но, как вы видите, это не совсем уместно.

@John: Я не думаю, что это имеет какое-то отношение к hash.

@John2: Карта-это немного обобщенно, вам не кажется? Для случая Фибоначчи все ключи являются смежными, так что вектор является подходящим, и снова есть гораздо более быстрые способы вычисления последовательности Фибоначчи, смотрите мой пример кода там.

Это называется мемуаризация, и есть очень хорошая статья о мемуаризации Мэтью Подвысоцки, опубликованная в эти дни. Он использует Фибоначчи, чтобы проиллюстрировать это. И показывает код в C# также. Прочтите это здесь .

Если вы используете C#, и можете использовать PostSharp , вот простой аспект запоминания для вашего кода:

[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
    private Dictionary<Object[], Object> _Cache;

    public MemoizeAttribute()
    {
        _Cache = new Dictionary<object[], object>(this);
    }

    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
    {
        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
        if (_Cache.ContainsKey(arguments))
        {
            eventArgs.ReturnValue = _Cache[arguments];
            eventArgs.FlowBehavior = FlowBehavior.Return;
        }
    }

    public override void OnExit(MethodExecutionEventArgs eventArgs)
    {
        if (eventArgs.Exception != null)
            return;

        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
    }

    #region IEqualityComparer<object[]> Members

    public bool Equals(object[] x, object[] y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (Int32 index = 0, len = x.Length; index < len; index++)
            if (Comparer.Default.Compare(x[index], y[index]) != 0)
                return false;

        return true;
    }

    public int GetHashCode(object[] obj)
    {
        Int32 hash = 23;

        foreach (Object o in obj)
        {
            hash *= 37;
            if (o != null)
                hash += o.GetHashCode();
        }

        return hash;
    }

    #endregion
}

Вот пример реализации Фибоначчи с его помощью:

[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Быстрая и грязная мемуаризация в C++:

Любой рекурсивный метод type1 foo(type2 bar) { ... } легко запоминается с помощью map<type2, type1> M .

// your original method
int fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
    if(n==0 || n==1)
        return 1;

    // only compute the value for fib(n) if we haven't before
    if(M.count(n) == 0)
        M[n] = fib(n-1) + fib(n-2);

    return M[n];
}

EDIT: @Konrad Рудольф
Конрад указывает, что std::map-это не самая быстрая структура данных, которую мы могли бы использовать здесь. Это верно, a vector<something> должен быть быстрее, чем a map<int, something> (хотя это может потребовать больше памяти, если входные данные для рекурсивных вызовов функции не были последовательными целыми числами, как в этом случае), но карты удобны для использования в целом.

Согласно Википедии Fib(0) должен быть равен 0, но это не имеет значения.

Вот простое C# решение с циклом for:

ulong Fib(int n)
{
  ulong fib = 1;  // value of fib(i)
  ulong fib1 = 1; // value of fib(i-1)
  ulong fib2 = 0; // value of fib(i-2)

  for (int i = 0; i < n; i++)
  {
    fib = fib1 + fib2;
    fib2 = fib1;
    fib1 = fib;
  }

  return fib;
}

Это довольно распространенный трюк, чтобы преобразовать рекурсию в хвостовую рекурсию ,а затем в цикл. Более подробно смотрите, например, эту лекцию (ppt).

Попробуйте использовать карту, где n-это ключ, а соответствующее ему число Фибоначчи-значение.

@Paul

Спасибо за информацию. Я этого не знал. Из упомянутой Вами ссылки на Википедию :

Это техника сохранения значений, которые уже были вычислены называется Мемоизация

Да я уже посмотрел код (+1). :)

Что это за язык такой? Он ничего не переполняет в c... Кроме того, можно попробовать создать таблицу поиска в куче или использовать карту

кэширование обычно является хорошей идеей для такого рода вещей. Поскольку числа Фибоначчи постоянны, вы можете кэшировать результат, как только вы его вычислите. Быстрый пример c / псевдокода

class fibstorage {


    bool has-result(int n) { return fibresults.contains(n); }
    int get-result(int n) { return fibresult.find(n).value; }
    void add-result(int n, int v) { fibresults.add(n,v); }

    map<int, int>   fibresults;

}


fib(int n ) {
    if(n==0 || n==1)
            return 1;

    if (fibstorage.has-result(n)) {
        return fibstorage.get-result(n-1);
    }

    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
           );
}


calcfib(n) {
    v = fib(n);
    fibstorage.add-result(n,v);
}

Это было бы довольно медленно, так как каждая рекурсия приводит к 3 поискам, однако это должно иллюстрировать общую идею

Является ли это сознательно выбранным примером? (напр. крайний случай, который вы хотите проверить)

Поскольку в настоящее время это O (1.6^n), я просто хочу убедиться, что вы просто ищете ответы на обработку общего случая этой проблемы (кэширование значений и т. д.), а не просто случайно пишете плохой код :D

Глядя на этот конкретный случай, вы могли бы иметь что-то вроде:

var cache = [];
function fib(n) {
    if (n < 2) return 1;
    if (cache.length > n) return cache[n];
    var result = fib(n - 2) + fib(n - 1);
    cache[n] = result;
    return result;
}

Который в худшем случае вырождается в O(n): D

[Edit: * не равно +: D ]

[Еще одно редактирование: версия Haskell (потому что я мазохист или что-то в этом роде)

fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n

]

@ESRogs:

std::map lookup - Это O (log n), что делает его здесь медленным. Лучше использовать вектор.

vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);

unsigned int fib(unsigned int n) {
    if (fib_cache.size() <= n)
        fib_cache.push_back(fib(n - 1) + fib(n - 2));

    return fib_cache[n];
}

Другие ответили на ваш вопрос хорошо и точно - вы ищете мемуаризацию.

Языки программирования с оптимизацией хвостового вызова (в основном функциональные языки) могут выполнять определенные случаи рекурсии без переполнения стека. Это не относится непосредственно к вашему определению Фибоначчи, хотя есть некоторые хитрости..

Формулировка вашего вопроса навела меня на интересную мысль.. Избегая переполнения стека чистой рекурсивной функции, сохраняя только подмножество кадров стека и перестраивая их при необходимости.. Только очень полезно в нескольких случаях. Если ваш алгоритм только условно полагается на контекст, а не на возврат, и / или вы оптимизируете для памяти, а не для скорости.

Еще одним отличным ресурсом для C# программистов для рекурсии, партиалов, карринга, мемуаризации и им подобных является блог Уэса Дайера, хотя он давно не публиковался. Он хорошо объясняет мемуаризацию, приводя здесь солидные примеры кода: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Mathematica имеет особенно гладкий способ запоминания, полагаясь на то, что хэши и вызовы функций используют один и тот же синтаксис:

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

Вот и все. Он кеширует (запоминает) fib[0] и fib[1] с места в карьер и кеширует rest по мере необходимости. Правила для вызовов функции сопоставления шаблонов таковы, что она всегда использует более конкретное определение перед более общим определением.

Если вы используете язык с первоклассными функциями, такими как Scheme, вы можете добавить memoization без изменения исходного алгоритма:

(define (memoize fn)
  (letrec ((get (lambda (query) '(#f)))
           (set (lambda (query value)
                  (let ((old-get get))
                    (set! get (lambda (q)
                                (if (equal? q query)
                                    (cons #t value)
                                    (old-get q))))))))
    (lambda args
      (let ((val (get args)))
        (if (car val)
            (cdr val)
            (let ((ret (apply fn args)))
              (set args ret)
              ret))))))


(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

Первый блок предоставляет средство запоминания, а второй блок-последовательность Фибоначчи, использующую это средство. Это теперь имеет o (n) время выполнения(в отличие от O (2^n) для алгоритма без запоминания).

Примечание: предоставленное средство запоминания использует цепочку closures для поиска предыдущих вызовов. В худшем случае это может быть O (n). Однако в этом случае искомые значения всегда находятся в верхней части цепочки, обеспечивая поиск O(1).

Проблема с этим кодом заключается в том, что он будет генерировать ошибку переполнения стека для любого числа больше 15 (в большинстве компьютеров).

Неужели? Какой компьютер вы используете? Это занимает много времени в 44, но стек не переполняется. Фактически, вы получите значение больше, чем может содержать целое число (~4 миллиарда без знака, ~2 миллиардов подписей), прежде чем стек будет переполнен (Fibbonaci(46)).

Это будет работать для того ,что вы хотите сделать, хотя (работает wiked быстро)

class Program
{
    public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
    static void Main(string[] args)
    {
        Console.WriteLine(Fibbonacci(46).ToString());
        Console.ReadLine();
    }

    public static int Fibbonacci(int number)
    {
        if (number == 1 || number == 0)
        {
            return 1;
        }

        var minus2 = number - 2;
        var minus1 = number - 1;

        if (!Items.ContainsKey(minus2))
        {
            Items.Add(minus2, Fibbonacci(minus2));
        }

        if (!Items.ContainsKey(minus1))
        {
            Items.Add(minus1, Fibbonacci(minus1));
        }

        return (Items[minus2] + Items[minus1]);
    }
}

Как показали другие плакаты, memoization -это стандартный способ обмена памятью на скорость, здесь есть некоторый псевдокод для реализации memoization для любой функции (при условии, что функция не имеет побочных эффектов):

Начальный код функции:

 function (parameters)
      body (with recursive calls to calculate result)
      return result

Это должно быть преобразовано в

 function (parameters)
      key = serialized parameters to string
      if (cache[key] does not exist)  {
           body (with recursive calls to calculate result)
           cache[key] = result
      }
      return cache[key]

Кстати Perl имеет модуль memoize , который делает это для любой функции в вашем коде, которую вы укажете.

# Compute Fibonacci numbers
sub fib {
      my $n = shift;
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
}

Для того чтобы запомнить эту функцию все что вы делаете это запускаете свою программу с помощью

use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)

@lassevk:

Это потрясающе, именно то, о чем я думал в своей голове, прочитав о мемуаризации в более высоком порядке Perl . Две вещи, которые я считаю полезными дополнениями:

1. Необязательный параметр для указания статического метода или метода-члена, используемого для создания ключа кэша.
2. Необязательный способ изменить объект кэша, чтобы можно было использовать дисковый или резервный кэш базы данных.

Не знаю, как это сделать с атрибутами (или если они вообще возможны с такой реализацией), но я планирую попробовать и выяснить.

(Не по теме: я пытался опубликовать это как комментарий, но я не понимал, что комментарии имеют такую короткую разрешенную длину, поэтому это действительно не подходит как 'answer')