Questo algoritmo dovrebbe essere eseguito in O (n)?

Question

Nota: Questo è problema 4,3 da Cracking Intervista Coding 5th Edition

Problema: Dato un ordinato (ordine crescente) array, scrivere un algoritmo per creare un albero binario di ricerca con l'altezza minima

Ecco il mio algoritmo, scritto in Java per fare questo problema

public static IntTreeNode createBST(int[] array) { 
     return createBST(array, 0, array.length-1); 
    } 
    private static IntTreeNode createBST(int[] array, int left, int right) { 
     if(right >= left) { 
      int middle = array[(left + right)/2; 
      IntTreeNode root = new IntTreeNode(middle); 
      root.left = createBST(array, left, middle - 1); 
      root.right = createBST(array, middle + 1, right); 
      return root; 
     } else { 
      return null; 
     } 
    } 

ho controllato questo codice contro l'autore del ed è quasi identico.
Tuttavia, sto attraversando un periodo difficile con l'analisi della complessità temporale di questo algoritmo.
So che non funzionerebbe in O (logn) come Binary Search perché non stai facendo la stessa quantità di lavoro ad ogni livello di ricorsione. E.G al primo livello, 1 unità di lavoro, 2 ° livello - 2 unità di lavoro, 3 ° livello - 4 unità di lavoro, fino a registrare (n) livello - n unità di lavoro.

Quindi in base al largo che, il numero di passi questo algoritmi prende sarebbe superiore delimitata da questa espressione matematica

che dopo aver visto Infinite geometric series, ho valutato a

o 2n che sarebbe in O (n)

Siete d'accordo con il mio lavoro qui e che questo algoritmo sarebbe eseguito in O (n) o mi sono perso qualcosa o effettivamente eseguito in O (nlogn) o qualche altra classe di funzione?

Answer 1

A volte è possibile semplificare i calcoli calcolando la quantità di tempo per articolo nel risultato anziché risolvere le relazioni di ricorrenza. Questo trucco si applica qui. Inizia modificando il codice a questa forma, ovviamente, equivalente:

private static IntTreeNode createBST(int[] array, int left, int right) { 
    int middle = array[(left + right)/2; 
    IntTreeNode root = new IntTreeNode(middle); 
    if (middle - 1 >= left) { 
     root.left = createBST(array, left, middle - 1); 
    } 
    if (right >= middle + 1) { 
     root.right = createBST(array, middle + 1, right); 
    } 
    return root; 
} 

Ora ogni chiamata a createBST crea direttamente 1 nodo. Poiché nella struttura finale ci sono n nodi, ci devono essere n chiamate totali a createBST e poiché ogni chiamata esegue direttamente una quantità costante di lavoro, la complessità temporale complessiva è O (n).

Answer 2

Se e quando si confonde in ricorsione, sostituire la chiamata ricorsiva (mentalmente, ovviamente) come un ciclo. Ad esempio, nella funzione precedente, è possibile immaginare le chiamate ricorsive all'interno di un "ciclo while". Dato che ora è un ciclo while eseguito fino al momento in cui tutti gli n nodi sono attraversati, la complessità è O (n).