La notación Big-O se usa para representar los límites superiores asintóticos. Describe la complejidad temporal o espacial relevante de los algoritmos. El análisis Big-O proporciona una estimación aproximada y simplificada de una dificultad problemática.
En cada entrevista en la que he estado, he sido interrogado sobre el análisis matemático de la complejidad, incluida la notación big-O. ¿Qué tan relevante es el análisis big-O para el desarrollo en la industria? ¿Con qué frecuencia lo usa realmente y qué tan necesario es tener una mentalidad...
A uno de mis amigos se le hizo esta pregunta de entrevista: "Hay un flujo constante de números que provienen de una lista infinita de números de los cuales necesita mantener una estructura de datos para devolver los 100 números más altos en cualquier momento dado. Suponga que todos los números...
Estoy tratando de enseñarme a mí mismo cómo calcular la notación BigO para una función arbitraria. Encontré esta función en un libro de texto. El libro afirma que la función es O (n 2 ). Da una explicación de por qué esto es así, pero estoy luchando por seguirlo. Me pregunto si alguien podría...
Anoche estaba discutiendo con otro programador que, aunque algo puede ser O (1), una operación que es O (n) puede superarlo si hay una gran constante en el algoritmo O (1). No estuvo de acuerdo, así que lo traje aquí. ¿Hay ejemplos de algoritmos que superen en gran medida a los de la clase a...
Estoy tratando de entender estas clasificaciones y por qué existen. ¿Es correcto mi entendimiento? Si no, ¿qué? P es la complejidad polinómica, o para algún número real no negativo , como , etc. Si un problema pertenece a P, entonces existe al menos un algoritmo que puede resolverlo desde cero en...
¡Ayuda! Tengo una pregunta donde necesito analizar el Big-O de un algoritmo o algún código. No estoy seguro de qué es Big-O o cómo se relaciona con Big-Theta u otros medios para analizar la complejidad de un algoritmo. No estoy seguro de si Big-O se refiere al tiempo para ejecutar el código, o la...
He estado aprendiendo más sobre la notación Big O y cómo calcularla en función de cómo se escribe un algoritmo. Encontré un conjunto interesante de "reglas" para calcular una notación Big O de algoritmos y quería ver si estaba en el camino correcto o muy lejos. Notación O grande: N function(n) {...
Mergesort es un algoritmo de divide y vencerás y es O (log n) porque la entrada se reduce a la mitad repetidamente. Pero, ¿no debería ser O (n) porque aunque la entrada se reduce a la mitad en cada ciclo, cada elemento de entrada debe iterarse para hacer el intercambio en cada matriz dividida en...
Estoy actualizando mi Teoría CS, y quiero saber cómo identificar la complejidad de un algoritmo O (log n). Específicamente, ¿hay una manera fácil de identificarlo? Sé que con O (n), generalmente tienes un solo bucle; O (n ^ 2) es un doble bucle; O (n ^ 3) es un bucle triple, etc. ¿Qué tal O (log...
Dado son dos matrices ordenadas una , b de tipo T con el tamaño de 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 simple. Simplemente tome de la matriz con el primer...
¿Qué es Big y O en notación Big O? He leído las definiciones y no dice qué se pronuncia O 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 que es un O
¿Qué término puedo usar para describir algo con complejidad O (N log N)? Por ejemplo: O (1): constante O (log N): logarítmico O (N): lineal O (N log N): ?????? O (N 2 ): Cuadrático O (N 3 ):
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...
La notación Big O proporciona un límite superior a una función, mientras que Big Theta proporciona un límite ajustado. Sin embargo, encuentro que la notación Big O es típicamente (e informalmente) enseñada y utilizada cuando realmente significan Big Theta. por ejemplo, "Quicksort es O (N ^ 2)"...
Cerrada . Esta pregunta está basada en la opinión . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que pueda ser respondida con hechos y citas editando esta publicación . Cerrado el año pasado ....
Estoy haciendo esta pregunta porque estoy confundido acerca de un aspecto con respecto a la notación O grande. Estoy usando el libro, Estructuras de datos y abstracciones con Java de Frank Carrano. En el capítulo sobre "Eficiencia de los algoritmos", muestra el siguiente algoritmo: int sum = 0,...
Dada cualquier función arbitrariamente doble recursiva, ¿cómo se calcularía su tiempo de ejecución? Por ejemplo (en pseudocódigo): int a(int x){ if (x < = 0) return 1010; else return b(x-1) + a(x-1); } int b(int y){ if (y <= -5) return -2; else return b(a(y-1)); } O algo por el...
Soy programador y acabo de empezar a leer Algoritmos. No estoy completamente convencido con las anotaciones, a saber, Bog Oh, Big Omega y Big Theta. La razón es, por definición de Big Oh, que establece que debería haber una función g (x) tal que siempre sea mayor o igual que f (x). O f (x) <= cn...
Estoy resolviendo una pregunta de algoritmo y mi análisis es que se ejecutaría en O (2 ^ sqrt (n)). ¿Como de grande es? ¿Equivale a O (2 ^ n)? ¿Sigue siendo tiempo no
Estoy acostumbrado a buscar la notación de Landau (Big O, Theta ...) de mis algoritmos a mano para asegurarme de que estén tan optimizados como sea posible, pero cuando las funciones se vuelven realmente grandes y complejas, está tomando forma demasiado tiempo para hacerlo a mano. También es...