Cuáles son las reglas para la “barrera Ω (n log n)” para los algoritmos de clasificación?
Escribí un programa simple que se ordena en O (n). Es altamente ineficiente de memoria, pero ese no es el punto.
tiliza el principio detrás de unaHashMap
para ordenar:
public class NLogNBreak {
public static class LinkedListBack {
public LinkedListBack(int val){
first = new Node();
first.val = val;
}
public Node first = null;
public void insert(int i){
Node n = new Node();
n.val = i;
n.next = first;
first = n;
}
}
private static class Node {
public Node next = null;
public int val;
}
//max > in[i] > 0
public static LinkedListBack[] sorted(int[] in, int max){
LinkedListBack[] ar = new LinkedListBack[max + 1];
for (int i = 0; i < in.length; i++) {
int val = in[i];
if(ar[val] == null){
ar[val] = new LinkedListBack(val);
} else {
ar[val].insert(val);
}
}
return ar;
}
}
Entonces esto cuenta como una especie de O (n), a pesar de que devuelve el resultado en un formato funky?