Il ciclo annidato può avere una complessità temporale lineare

Can nested loop have linear time complexity?

Sì. Considera questa funzione:

def linear_time(n):
    for i in range(sqrt(n)):
        for j in range(sqrt(n)):
            something_that_takes_constant_time()

La sua complessità temporale è O ( sqrt(n) * sqrt(n) ) = O ( n ).

Ricorda:

def foo(x):
    part_a(x)
    part_b(x)
    # if part_a(x) has a time complexity of O(f(x))
    # and if part_b(x) has a time complexity of O(g(x))
    # then foo(x) has a time complexity of O(f(x) + g(x))

def foo(x):
    loop f(x) times:
        part_of_loop(x)
    # if part_of_loop(x) has a time complexity of O(g(x))
    # then foo(x) has a time complexity of O(f(x) * g(x))

Quindi esaminiamo questo algoritmo:

Partition(a[], l, h)
{
    pivot = a[l]; # O(1)
    i = l; j = h; # O(1)
    while(i < j) # runs ??? times
    {
        while(a[i] <= pivot) # runs O(h - l) times
            i++; # O(1)
        while(a[j] > pivot) # runs O(h - l) times
            j--; # O(1)
        if(i < j) # O(1)
            swap(a[i], a[j]); # O(1)
    }
    swap(a[l], a[j]); # O(1)
    return j; # O(1)
}

Quindi la parte interna del ciclo ha una complessità temporale di O ((h - l) * 1 + (h - l) * 1 + 1 * 1) = O (h - l). Ma qual è la complessità temporale dell'intero ciclo? Viene eseguito tutte le volte che (i < j) è true.

La condizione post dopo while(a[i] <= pivot) è a[i] > pivot , e dopo while(a[j] > pivot) abbiamo a[j] <= pivot . Se i < j (l'unico caso che ci interessa, altrimenti il ciclo finirà comunque!), I valori dei due indici vengono scambiati, il che significa che a[i] <= pivot e a[j] > pivot saranno ancora una volta true. Quindi, quello che fa è trovare gli indici più a sinistra e più a destra che si trovano sul lato sbagliato del pivot e scambiarli, finché tutti non sono partizionati correttamente. Quindi quanto spesso funziona quel ciclo? Non possiamo davvero dire, dipende da quanti elementi si trovano sul lato "sbagliato" del pivot. Sappiamo che ogni ciclo dopo il primo i e j sarà almeno un passo più vicino l'uno all'altro, quindi il limite superiore sarà (h - l) / 2 + 1 che è di complessità O (h - l).

Ora, ho saltato qualcosa: il numero di volte che il ciclo esterno viene eseguito dipende dal numero di volte in cui il ciclo interno viene eseguito. Poiché il numero di volte che i loop interni tendono a spostarsi verso O (h - l), il numero di volte in cui il ciclo esterno tende verso 1 e viceversa. Sono una specie di divorarsi a vicenda. Il limite superiore che ho menzionato nel paragrafo precedente è ciò che otteniamo quando i loop interni girano solo una volta ogni volta, rendendo la loro complessità O (1). E si scopre che ogni volta che i cicli interni eseguono a e b rispettivamente, il numero di volte in cui il ciclo esterno viene eseguito in O((h - l) / (a + b) . In altre parole, la complessità del contenuto del ciclo esterno è O(a + b) e il numero di volte che il ciclo esterno esegue complessità O((h - l) / (a + b) , rendendo l'intero ciclo con una complessità temporale di O((h - l) / (a + b) * (a + b)) = O(h - l) , e quindi questa partizione funziona in tempo lineare.

(Penso che ci sia un bug qui: cosa succede se a[i] <= a[l] per tutto l <= i <= h ?)

I loop annidati sono in realtà irrilevanti per O. Ciò che conta è quante volte hai a che fare con un oggetto. In generale i tuoi loop definiscono il tuo annidamento, ma questo è un caso particolare in cui i loop diventano più piccoli mentre scorri verso il basso. (Si noti che se si seleziona in qualche modo un pivot molto cattivo ad ogni iterazione i loop non si restringono rapidamente e si finisce con un runtime O (n ^ 2). Scegliendo il primo elemento della lista ogni volta e provando ad ordinare già -la lista ordinata causerà questo.)