Generalmente, siempre hay más de una forma de resolver un problema en informática con diferentes algoritmos. Por lo tanto, es muy necesario utilizar un método para comparar las soluciones con el fin de juzgar cuál es la más óptima. El método debe ser: Independiente de la máquina y su configuración, en la que se ejecuta … Continue reading «Complejidad del tiempo y complejidad del espacio»
En este artículo, discutiremos la complejidad temporal del Algoritmo Euclidiano que es O(log(min(a, b)) y se logra. Algoritmo de Euclides : es un método eficiente para encontrar el MCD (máximo común divisor) de dos números enteros. La complejidad temporal de este algoritmo es O(log(min(a, b)) . Recursivamente se puede expresar como: gcd(a, b) = gcd(b, … Continue reading «Complejidad temporal del algoritmo euclidiano»
La idea básica detrás de este método es adivinar la respuesta y luego demostrar que es correcta por inducción. Este método se puede utilizar para resolver cualquier recurrencia. Si se adivina una solución y luego se intenta verificar nuestra suposición de manera inductiva, por lo general, la prueba tendrá éxito (en ese caso hemos terminado) … Continue reading «Método de adivinar y confirmar»
Pre-requisite: Sieve of Eratosthenes What is Sieve of Eratosthenes algorithm? In order to analyze it, let’s take a number n and the task is to print the prime numbers less than n. Therefore, by definition of Sieve of Eratosthenes, for every prime number, it has to check the multiples of the prime and mark it … Continue reading «¿Cómo es que la complejidad temporal de la criba de Eratóstenes es n*log(log(n))?»
El teorema de Master es un método popular para resolver recurrencias de complejidad temporal de la forma: Con restricciones sobre a, b y f(n). La forma de relación de recurrencia limita la usabilidad del teorema de Master. Las siguientes son tres recurrencias que no se pueden resolver directamente usando el teorema de Master: Método Akra-Bazzi … Continue reading «Método Akra-Bazzi para encontrar las complejidades temporales»
¿Cuál es la complejidad temporal de la siguiente función? C++ void fun(int n, int k) { for (int i = 1; i <= n; i++) { int p = pow(i, k); for (int j = 1; j <= p; j++) { // Some O(1) work } } } // This code is contributed by … Continue reading «Complejidad temporal del bucle con potencias»
Un montón mínimo es un árbol binario completo en el que los Nodes secundarios tienen un valor más alto (menor prioridad) que los Nodes principales, es decir, cualquier ruta desde la raíz hasta los Nodes hoja tiene un orden ascendente de elementos. En el caso de un árbol binario, se considera que la raíz está … Continue reading «Análisis de complejidad de varias operaciones de Binary Min Heap»
Requisito previo: notaciones asintóticas Complejidad del tiempo: La complejidad del tiempo es el tiempo que necesita un algoritmo expresado como una función del tamaño de un problema. También se puede definir como la cantidad de tiempo de computadora que necesita para ejecutar un programa hasta su finalización. Cuando resolvemos un problema de complejidad de tiempo, … Continue reading «Problemas misceláneos de la complejidad del tiempo»
La palabra “ podar ” significa reducir algo quitando cosas que no son necesarias. Entonces, Prune-and-Search es un excelente paradigma algorítmico para resolver varios problemas de optimización. Este enfoque fue sugerido por primera vez por Nimrod Megiddo en 1983 . Este enfoque siempre consta de varias iteraciones. En cada iteración, descarta una fracción, digamos f, … Continue reading «Podar y buscar | Una descripción general del análisis de complejidad»