tempo di esecuzione di nested mentre si esegue il ciclo all'interno di loop

0

Sono qui per chiarire la mia comprensione dei tempi di esecuzione di questi 2 algoritmi:

Algorithm1(n):
For i = 1 to n
    j = 1
    while i+j < n
        j = j+1

e

Algorithm2(n):
For i = 1 to n
    j = 1
    while i*j < n
        j = j+1

Il primo algoritmo credo sia O(n) perché il ciclo interno è limitato da n e la condizione while viene incrementata linearmente quando i viene incrementata dal ciclo for esterno. Altrimenti, direi O(n^2) se sbaglio.

Il secondo algoritmo credo sia O(log(n^2)) perché, con il crescere di i , la quantità di iterazioni diminuirà nel ciclo while che è controllato dal ciclo for esterno.

    
posta Apprentice Programmer 04.01.2015 - 22:12
fonte

1 risposta

6

Il tuo primo algoritmo è O (n ^ 2), poiché il ciclo esterno viene eseguito n volte, e in media il ciclo interno viene eseguito n / 2 volte; scartiamo il fattore costante in quanto ci interessa solo il comportamento asintotico.

Il mio secondo algoritmo è O (n log n): il ciclo esterno viene eseguito n volte, quindi nella risposta deve esserci un fattore di n e credo che il ciclo interno esegua log n volte in media.

Si noti che la risposta suggerita di O (log (n ^ 2)) non è una risposta valida in ogni caso: log (n ^ 2) = 2 log n, quindi O (log (n ^ 2)) dovrebbe essere semplificato a O (log n).

    
risposta data 04.01.2015 - 22:26
fonte

Leggi altre domande sui tag