Ho visto in molti luoghi, la complessità per bubble sort è O (n).Complexity of Bubble Sort
Ma come può essere così perché il ciclo interno dovrebbe sempre eseguire volte n-i.
for (int i = 0; i < toSort.length -1; i++) {
for (int j = 0; j < toSort.length - 1 - i; j++) {
if(toSort[j] > toSort[j+1]){
int swap = toSort[j+1];
toSort[j + 1] = toSort[j];
toSort[j] = swap;
}
}
}
E qual è il valore "medio" di n-i? n/2
modo che venga eseguito in O(n*n/2) che è considerato come O (n)
Poiché il ciclo viene eseguito esterno n volte e per ogni iterazione ciclo viene eseguito interne (ni) volte, il numero totale di operazioni può essere calcolato come n * (ni) = O (n2).
Esistono diversi tipi di complessità temporale: si utilizza la notazione O grande, pertanto tutti i casi di questa funzione saranno almeno una volta complessità.
Mentre si avvicina all'infinito, questo può essere fondamentalmente uno scenario peggiore di 2^complessità temporale. La complessità del tempo non è un'arte esatta, ma più un campo da baseball per quale tipo di velocità ci si può aspettare per questa classe di algoritmi e quindi si sta tentando di essere troppo precisi.
Ad esempio la complessità temporale teorica potrebbe benissimo essere n^2 anche se in teoria dovrebbe essere n * n-1 a causa di qualsiasi imprevisto sovraccarico di elaborazione potrebbe essere eseguita.
È O (n^2), perché lunghezza * lunghezza.
Ma perché non abbiamo quel "/ 2" –
@DeepakKumar perché non ha significato quando si ha a che fare con la scala. La grande notazione O riguarda la scala. Prenderesti in considerazione O (n) per essere diverso da O (n-1)? anche se n! = n-1 hanno la stessa scala. Lo stesso vale per 'n/2' e' n'. – alfasin
Grazie alfasin. :) –