Informazioni su Big O

Question

Dato il seguente codice, qual è la complessità di 3. e in che modo rappresenterei algoritmi semplici con le seguenti complessità?

O (n² + n)
O (n² + 2n)
O (log n) O (nlogn)

var collection = new[] {1,2,3}; 
var collection2 = new[] {1,2,3}; 

//1. 
//On 
foreach(var i in c1) 
{ 
} 

//2. 
//On² 
foreach(var i in c1) 
{ 
    foreach(var j in c1) 
    { 
    } 
} 

//3. 
//O(nⁿ⁺ᵒ)? 
foreach(var i in c1) 
{ 
    foreach(var j in c2) 
    { 
    } 
} 

Answer 1

L'esterno foreach viene eseguito n = | c1 | volte (dove | x | è la dimensione di c1), mentre l'interno foreach viene eseguito m = | c2 | volte. Ecco O (n * m) volte in totale.

---

Come potrei rappresentare semplici algoritmi con le seguenti complessità?

• O (n² + n)

Questa è la stessa di O (n^2). Qualcosa che richiede O (n^2) tempo sarebbe bere un brindisi con ogni altra persona a una festa, assumendo che ci siano sempre esattamente due persone in un brindisi, e solo una persona fa la tostatura alla volta.

• O (n² + 2n)

Idem come sopra; il termine O (n^2) domina. Un altro esempio di uno sforzo di O (n^2) è piantare alberi in un giardino quadrato di lunghezza n, supponendo che sia necessario un tempo costante per piantare ogni albero, e che una volta piantato un albero altri alberi siano esclusi dalla sua vicinanza.

• O (log n)

Un esempio di questo sarebbe trovare una parola in un dizionario ripetutamente raccogliendo il punto centrale della regione di pagine necessarie per la ricerca successiva. (In altre parole, una ricerca binaria.)

• O (nlogn)

Utilizzare l'algoritmo di cui sopra, ma ora bisogna trovare ogni parola nel dizionario.

Answer 2

3 è O (n * m), oppure O (n^2) se le due collezioni hanno la stessa dimensione.

O (n^2 + n) è inutile perché n è minore di n^2. Basta scrivere O (n^2).

Gli algoritmi decenti comparison sort vengono eseguiti su O (n * log (n)). Se non ne conosci nessuno, guarda su Wikipedia.

A binary search è O (log (n)).

Answer 3

La complessità di 3 è O (m * n). Nessuna complessità O (n + n) o O (n + 2n).È solo O (n). Questo perché n is o (n).

Esempio di O (log (n)) è la ricerca binaria.

Esempio di O (n * log (n)) è un tipo di unione.

Answer 4

Non c'è O (n² + n) o O (n^2 + 2n). Tralasciando la maggior parte dei fondamenti matematici della complessità algoritmica, devi almeno sapere che è "atipico". Mentre N si avvicina all'infinito, il valore di n^2 + n è dominato dal termine n^2, quindi questa è la complessità asintotica di n^2 + n.

La complessità di 3 è O (I * J), dove I e J sono le dimensioni degli ingressi in c1 e c2.

Answer 5

A dire il vero O (n² + n) & O (n² + 2n) sono uguali.