differenza tra crescita esponenziale e logaritmica

Stai fraintendendo il significato. Probabilmente stanno parlando della complessità di un algoritmo, che non ha nulla a che fare con la conseguente sequenza di numeri (di cui sembra parlare).

Guarda alcuni frammenti.

Confronta per esempio for(k=1;k<=5000;k*=2) con for(k=1;k<=10000;k*=2) . Vedrai che il secondo richiederà solo 1 altra ripetizione. In effetti il raddoppio del n richiederà sempre un solo incremento.

Ora vediamo l'algoritmo per la sequenza di Fibonacci di cui probabilmente si parlava:

int fibonacci(int n)  {
    if(n <= 1) return n;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}

Ora vediamo quanto spesso la funzione viene eseguita per diversi valori per n :

n = 0:  1    function call
n = 1:  1   function call
n = 2:  3   function calls
n = 3:  5   function calls
n = 4:  9   function calls
n = 5:  15  function calls
n = 6:  25  function calls
n = 7:  41  function calls
n = 8:  67  function calls
n = 9:  109 function calls
n = 10: 177 function calls

In effetti hai ottenuto la chiamata a una funzione che effettui quando chiami fibonacci(n) + la quantità di chiamate a funzioni eseguite in fibonacci(n-1) + la quantità di chiamate a funzioni in fibonacci(n-2) .
Pertanto aumentare di poco la n farebbe un enorme aumento del numero di chiamate di funzione effettivamente fatte.

Per il primo frammento, sei corretto, la sequenza è 1, 2, 4, 8, ma ti manca il punto. Crea una tabella, n e il numero di passaggi da eseguire. Esempio:

n / lunghezza della sequenza

1 / 1
2 / 2
4 / 3
8 / 4
16 / 5

Come puoi vedere, ottieni O (log n).

Per Fibonacci, hai f (n) = f (n-1) + f (n-2). Per ogni n passo, calcoli altri 2 passaggi. Per ogni passo n-1 devi calcolare anche 2 passaggi. Ti fermi su n = 1 o n = 2, l'ultimo con 2 passaggi in più n = 3. Per nth step, hai, più o meno:

2^3 + 2^4 + .. + 2^(n-1) = 2^n - 2^0 - 2^1 - 2^2 = O(2^n)

La crescita asintotica non riguarda il modo in cui i numeri nella sequenza crescono: si tratta di quanto tempo occorre per calcolare la sequenza per un dato n .

Nel caso di for(k=1;k<=n;k*=2) , richiede solo una singola iterazione per calcolare n*2 rispetto a n , quindi supponendo che il tempo di esecuzione dell'iterazione sia O(1) , la crescita è logaritmica.

Nel caso di Fibonacci, se usi l'algoritmo ricorsivo ingenuo, ci vuole il doppio del tempo per calcolare n+1 rispetto a n , quindi la crescita è esponenziale.

Solo un'osservazione sulla complessità del calcolo dei numeri di Fibonacci. Come altri hanno sottolineato, l'implementazione ingenua

int fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

è esponenziale. D'altra parte, la seguente implementazione è lineare:

int fibonacci_helper(int f0, int f1, int p, int n)
{
    if (p == n)
        return f0 + f1;
    else
        return fibonacci_helper(f1, f0 + f1, p + 1, n);
}

int fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return fibonacci_helper(0, 1, 2, n);
}