Ricorsione e Big O

Question

Ho lavorato a un recente compito di Informatica che coinvolge ricorsione e notazione O-big. Credo di averlo capito abbastanza bene (certamente non perfettamente, però!) Ma c'è una domanda in particolare che mi sta dando più problemi. La cosa strana è che, guardandolo, sembra essere il più semplice a fare i compiti.

Fornisci il miglior tasso di crescita usando la notazione big-Oh per la soluzione alla seguente ricorrenza?

T (1) = 2

T (n) = 2T (n - 1) + 1 per n > 1

E le scelte sono:

• O (n log n)
• O (n ^ 2)
• O (2 ^ n)
• O (n ^ n)

Comprendo che la grande O funziona come limite superiore, per descrivere la maggior parte dei calcoli, o il tempo di esecuzione più elevato, che il programma o il processo richiederà. Sento che questa particolare ricorsione dovrebbe essere O (n), poiché, al massimo, la ricorsione si verifica una sola volta per ogni valore di n. Poiché n non è disponibile, è meglio di così, O (nlogn), o peggio, essendo le altre tre opzioni.

Quindi, la mia domanda è: perché non è questa O (n)?

Answer 1

Esistono un paio di modi diversi per risolvere le ricorrenze: sostituzione, albero di ricorrenza e teorema del maestro. Il teorema principale non funzionerà nel caso, perché non si adatta alla forma del teorema principale.

Potresti usare gli altri due metodi, ma il modo più semplice per risolvere questo problema è iterativamente.

T (n) = 2T (n-1) + 1
T (n) = 4T (n-2) + 2 + 1
T (n) = 8T (n-3) + 4 + 2 + 1
T (n) = ...

Vedi lo schema?

T (n) = 2 ^n-1 & # 8901; T (1) + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ^n-1 & # 8901; 2 + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

Pertanto, il limite più stretto è & # 920; (2 ⁿ ).

Answer 2

Penso che tu abbia frainteso un po 'la domanda. Non ti chiede quanto tempo ci vorrebbe per risolvere la ricorrenza. Si sta chiedendo quale sia il big-O (il limite asintotico) della soluzione stessa.

Quello che devi fare è trovare una soluzione a forma chiusa, i. e. la formula non ricorsiva per T (n) e quindi determinare qual è il big-O di quell'espressione.

Answer 3

La domanda è chiedere la notazione big-Oh per la soluzione della ricorrenza, non il costo del calcolo della ricorrenza.

In altre parole: la ricorrenza produce:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

Quale notazione big-Oh descrive meglio la sequenza 2, 5, 11, 23, 47, ...

Il modo corretto di risolvere è quello di risolvere le equazioni di ricorrenza.

Answer 4

Penso che questo sarà esponenziale. Ogni incremento su n rende il valore più grande del doppio.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T (x) sarebbe il tempo di esecuzione del seguente programma (ad esempio):

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Answer 5

  

Penso che questo sarà esponenziale. Ogni incremento su n porta il doppio del calcolo.

No, non lo fa. Al contrario:

Considera che per le iterazioni n , otteniamo il tempo di esecuzione R . Quindi per n + 1 iterazioni otterremo esattamente R + 1.

Pertanto, il tasso di crescita è costante e il tempo di esecuzione complessivo è in effetti O ( n ).

Tuttavia, penso che l'ipotesi di Dima sulla domanda sia giusta, sebbene la sua soluzione sia eccessivamente complicata:

  

Quello che devi fare è trovare una soluzione a forma chiusa, i. e. la formula non ricorsiva per T (n) e quindi determinare qual è il big-O di quell'espressione.

È sufficiente esaminare la dimensione relativa di T ( n ) e T ( n + 1) iterazioni e determinare il tasso di crescita relativo. L'importo raddoppia ovviamente il che dà direttamente la crescita asintotica.

Answer 6

Prima di tutto, tutte e quattro le risposte sono peggiori di O (n) ... O (n * log n) è più complesso della semplice O (n). Cosa c'è di più grande: 8 o 8 * 3, 16 o 16 * 4, ecc ...

Passa alla domanda reale. La soluzione generale può ovviamente essere risolta in tempo costante se non si esegue la ricorsione

(T (n) = 2 ^ (n - 1) + 2 ^ (n) - 1), quindi non è quello che stanno chiedendo.

E come puoi vedere, se scriviamo il codice ricorsivo:

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

Ovviamente è O (n).

Quindi, sembra essere una domanda mal formulata, e probabilmente ti stanno chiedendo la crescita della funzione stessa, non la complessità del codice. Sono 2 ^ n. Ora vai a fare il resto dei tuoi compiti ... e studia su O (n * log n)

Answer 7

Calcolare una soluzione in formato chiuso per la ricorsione è facile. Per ispezione, indovini che la soluzione è

T(n) = 3*2^(n-1) - 1

Quindi, per induzione, dimostri che questa è davvero una soluzione. Caso di base:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

induzione:

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

dove la prima uguaglianza deriva dalla definizione di ricorrenza, e il secondo dall'ipotesi induttiva. QED.

3 * 2 ^ (n-1) - 1 è chiaramente Theta (2 ^ n), quindi la risposta giusta è la terza.

Alle persone che hanno risposto a O (n): non potrei essere più d'accordo con Dima. Il problema non richiede il limite superiore più stretto alla complessità computazionale di un algoritmo per calcolare T (n) (che ora sarebbe O (1), poiché è stata fornita la sua forma chiusa). Il problema richiede il limite superiore più stretto su T (n) stesso , ed è quello esponenziale.