Complejidad del algoritmo
Hola, estoy estudiando en informatica en la UPM y estoy haciendo un trabajo sobre la complejidad de un metodo de busqueda que es el siguiente:
static void stupidSort(int array[], int tamanio)
{
int i=0, aux, cont=0;
while (i < tamanio-1) {
if (array[i+1] < array[i]) {
aux = array[i];
array[i] = array[i+1];
array[i+1] = aux;
i = 0;
} else{
i++;
}
}
}
Segun lo que he investigado, este metodo en el mejor de los casos, es decir, con el vector ordenado, su complejidad seria O(n) y si esta toltamente desordenado deberia ser O(n*n!), porque recorre n veces el algoritmo y n! porque esta intercambiando todo los elementos.
Me gustaria saber si estoy acertado o me equivoco.
Gracias.
static void stupidSort(int array[], int tamanio)
{
int i=0, aux, cont=0;
while (i < tamanio-1) {
if (array[i+1] < array[i]) {
aux = array[i];
array[i] = array[i+1];
array[i+1] = aux;
i = 0;
} else{
i++;
}
}
}
Segun lo que he investigado, este metodo en el mejor de los casos, es decir, con el vector ordenado, su complejidad seria O(n) y si esta toltamente desordenado deberia ser O(n*n!), porque recorre n veces el algoritmo y n! porque esta intercambiando todo los elementos.
Me gustaria saber si estoy acertado o me equivoco.
Gracias.