Tengo el siguiente algoritmo que encuentra duplicados y los elimina:
public static int numDuplicatesB(int[] arr) {
Sort.mergesort(arr);
int numDups = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == arr[i - 1]) {
numDups++;
} }
return numDups;
}
Estoy tratando de encontrar la peor complejidad de tiempo en este caso. Sé que mergesort es nlog(n), y en mi bucle for estoy iterando sobre todo el conjunto de datos para que eso cuente como n. Sin embargo, no estoy seguro de qué hacer con estos números. ¿Debería resumirlos juntos? Si tuviera que hacer eso, ¿cómo lo haría?
algorithms
algorithm-analysis
big-o
chopper draw lion4
fuente
fuente
Respuestas:
Para la complejidad de Big O, lo único que le importa es el término dominante.
n log(n)dominanasí que ese es el único término que te importa.fuente
f(n) is O(g(n))lo que realmente estamos diciendo es que la funciónf is a member of the set of functions that grows at the rate of at most g(n) over the long term. Esto significa que todos los miembros deO(n)son también miembros deO(n*log(n)). Las+expresiones en como seO(f(n)) + O(g(n))refieren realmente a la unión de conjuntos (cuál de ustedes es realmente pedante, realmente debería usar ∪).A + B = { a + b | a in A, b in B }. Sucede que para conjuntos de la formaO(g(n))esto es lo mismo que la unión de conjuntos, ya que uno de los conjuntos es siempre un subconjunto del otro, y ambos son invariables a las sumas (es decir, A + A = A). (Vaya, Nate escribió esencialmente lo mismo).Razonemos nuestro camino y recordemos la definición de
O. El que voy a usar es para el límite en el infinito.Tiene razón al afirmar que realiza dos operaciones con los límites asintóticos correspondientes de
O(n)y,O(nlog(n))pero combinarlos en un solo límite no es tan simple como agregar las dos funciones. Usted sabe que su función lleva al menosO(n)tiempo y también al menosO(nlog(n))tiempo. Entonces, realmente la clase de complejidad para su función es la unión deO(n)y,O(nlog(n))peroO(nlog(n))es un superconjunto de,O(n)así que realmente es justaO(nlog(n)).fuente
Si fuera a exponerlo a mano, se vería más o menos así:
Supongamos que el tiempo total es: an + bn log (n), donde a y b son constantes (ignorando los términos de orden inferior).
Cuando n va al infinito (an + bn log (n)) / n log (n) -> a / log (n) + b -> b
Entonces, el tiempo total es O (bn log (n)) = O (n log (n)).
fuente
Comience con la definición de O ():
O (n log n) significa "menor que C n log n, si n es grande".
O (n) significa "menor que D n, si n es grande".
Si agrega ambos, el resultado es menor que C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).
En general, si f (n)> C g (n) para n grande y algo de C> 0, entonces O (f (n)) + O (g (n)) = O (f (n)). Y después de hacer algunos casos usando la definición de O (), sabrá lo que puede y no puede hacer.
fuente
La gran notación O se define como un conjunto:
Por lo tanto,
contiene todas las funciones que son, a partir de un punto grande arbitrario 
, siempre más pequeñas que g.
Ahora, cuando tiene una función que está dentro
y luego ejecuta otra que aumenta más lentamente que g, ciertamente aumenta más lentamente que 2g. Por lo tanto, ejecutar algo más lento que g no cambiará la clase de complejidad.
Más formalmente:
Puedes probarlo fácilmente.
TL; DR
Aún es
fuente