Notazione Big O per l'algoritmo

Naviga le tue risposte
0

Quale sarebbe il grande o per il algo: 

for (i=0; i < n*n; i++)
  for(j=0; j<i*i; j++)

Come da mia comprensione
Il primo ciclo andrà in loop fino a n 2 volte.
Il secondo ciclo andrà in giro per n 2 volte.

Ho ragione o è una rappresentazione di O (n 6 )?

C'è anche un modo semplice per dire quando usare il registro. Ho assunto che ogni volta che la variabile di loop viene moltiplicata si applica la funzione ln

ad es .: for (i=1; i<n*n i=i*2) Big o per il ciclo secondo la mia comprensione è O (ln n 2 ) (Ho ancora ragione?)

    
posta new 07.10.2014 - 19:40
fonte

1 risposta

2

Queste sono 2 domande distinte.

1) Sì, questo è O (n ^ 6). Puoi, infatti, calcolare direttamente il numero di iterazioni, il ciclo interno rende i ^ 2 iterazioni, quindi sum i^2 for i from 0 to n^2 . Inseriscilo in Wolfram Alpha o Matlab e ottieni 1/6 * n^2 * (n^2 + 1) * (2 * n^2 + 1)

2) È un utile mnemonico . Sì, un log si presenta naturalmente quando conti il numero di volte che devi moltiplicare qualcosa da solo per ottenere qualcos'altro. Tuttavia, non è l'unico posto in cui sorge. Inoltre, O(ln(n^2)) = O(2 * ln(n)) = O(ln(n))

    
risposta data 07.10.2014 - 19:58
fonte

Leggi altre domande sui tag

Come distribuire le risorse protette da copyright con e il progetto open source? In che modo Google gestisce il loro certificato SSL di Google Immagini?