La complessità temporale di un algoritmo [chiuso]

Nonostante l'apparente semplicità della domanda, penso che sia piuttosto difficile.

... Vado fino a dire che non può essere espresso nella notazione "big O" ... o almeno non nel solito senso con i log e gli esponenziali.

Lasciami spiegare. In termini di notazione "big O", dovresti essere in grado di sapere quanti passaggi sono richiesti in termini di n . Per fare ciò, devi sapere quando il tuo i supera n .

Consentitemi di rinominarlo in f per la normale notazione matematica e j del numero di iterazioni. Questo si riduce alla soluzione della formula ricorsiva:

f(j) = 2^f(j-1)

... che non ha alcuna soluzione che possa essere espressa in termini di "funzioni elementari" di j (il numero di passaggi) in base a:

link

Modifica

Sarebbe un grande O usando questa notazione:

link

Ovviamente andrò tra i valori 1 e 3 perché 2 ^ 1 == 3 e 2 ^ 3 == 1. Il ciclo avrà zero iterazioni (un test) se n ≤ 1, una iterazione (due test) se n = 2 o n = 3, e funzionerà all'infinito altrimenti.

questa è un'iterazione, quindi dobbiamo aprire il ciclo dì che sto prendendo valore da 1 a 2 ^ k nel modello 1,2,4,8,16 .... 2 ^ k cioè 2 ^ 0,2 ^ 1,2 ^ 2,2 ^ 3 in questo modo dove la somma viene eseguita k volte fino a 2 ^ k è uguale a n 2 ^ k = n k = logn e è O (log n) e anche il caso peggiore è lo stesso, quindi l'ans sarà Theta (logn)