Preguntas con etiqueta 'big-o'

11
respuestas

Obtén los 100 números más altos de una lista infinita

A uno de mis amigos se le hizo esta pregunta de la entrevista -    "Hay un flujo constante de números provenientes de alguna lista infinita   de los números de los cuales necesita mantener una estructura de datos para   devuelve los 100 númer...
hecha 26.10.2011 - 09:59
20
respuestas

¿Existen algoritmos del mundo real que superen en gran medida a la clase siguiente? [cerrado]

Anoche estuve discutiendo con otro programador que, aunque algo puede ser O (1), una operación que es O (n) puede superarla si existe una gran constante en el algoritmo O (1). No estuvo de acuerdo, así que lo he traído aquí. ¿Existen ejemplos...
hecha 07.10.2011 - 19:31
5
respuestas

¿Es esta una “regla” adecuada para identificar la notación “O grande” de un algoritmo?

He estado aprendiendo más sobre Big O Notation y cómo calcularlo en función de cómo se escribe un algoritmo. Me encontré con un interesante conjunto de "reglas" para calcular una notación Big O de algoritmos y quería ver si estoy en el camino co...
hecha 09.04.2013 - 15:51
5
respuestas

Determinar si un algoritmo es O (log n)

Estoy actualizando mi teoría de CS, y quiero saber cómo identificar esa complejidad de algoritmo O (log n). Específicamente, ¿hay una manera fácil de identificarlo? Sé que con O (n), normalmente tienes un solo bucle; O (n ^ 2) es un bucle dob...
hecha 26.04.2012 - 02:46
2
respuestas

Algoritmo para combinar dos matrices ordenadas con un número mínimo de comparaciones

Se dan dos matrices ordenadas a , b de tipo T con tamaño n y m . Estoy buscando un algoritmo que combine las dos matrices en una nueva matriz (de tamaño máximo n + m). Si tiene una operación de comparación barata, esto es bastante sim...
hecha 26.12.2014 - 13:15
4
respuestas

Cuando hablo, ¿cómo puedo decir que el orden de complejidad de un algoritmo es O (N log N)?

¿Qué término puedo usar para describir algo con complejidad O (N log N)? Por ejemplo: O (1): Constante O (registro N): logarítmica O (N): Lineal O (N log N): ?????? O (N 2 ): Quadratic O (N 3 ): cúbico
hecha 18.07.2015 - 09:01
5
respuestas

Algoritmos: ¿Cómo sumar O (n) y O (nlog (n)) juntos?

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]) {...
hecha 08.10.2014 - 22:59
7
respuestas

¿Qué es O en Big O?

¿Qué es Big y O en la notación Big O? He leído las definiciones y no dice qué es O pronunciado como 'oh'. Por ejemplo, entiendo que O (n) es la complejidad de un algoritmo lineal donde n podría ser el número de operaciones. pero ¿qué es una...
hecha 13.09.2011 - 20:03
6
respuestas

¿Cómo lo llamas cuando cambias el tiempo de ejecución Big O de una función [cerrado]?

Digamos que tengo una función que ordena una base de datos en O(n^2) time. Quiero proceder a refactorizarlo para que se ejecute en tiempo de O(n log(n)) y, al hacerlo, cambiaré la forma fundamental en que se ejecuta la operación, m...
hecha 07.01.2018 - 15:23
4
respuestas

¿Por qué mergesort O (log n)?

Mergesort es un algoritmo de dividir y conquistar y es O (log n) porque la entrada se reduce a la mitad en varias ocasiones. Pero, ¿no debería ser O (n) porque a pesar de que la entrada se reduce a la mitad en cada bucle, cada elemento de entrad...
hecha 13.09.2015 - 20:31