Prerrequisito: Análisis de Algoritmos | Análisis O grande En el artículo anterior , se discute el análisis del algoritmo utilizando la notación asintótica Big O. En este artículo, se discuten algunos ejemplos para ilustrar la notación de complejidad de tiempo de Big O y también aprender a calcular la complejidad de tiempo de cualquier programa. … Continue reading «Ejemplos de análisis Big-O»
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»
Problema SAT : SAT (Boolean Satisfiability Problem) es el problema de determinar si existe una interpretación que satisfaga una fórmula booleana dada. Pregunta si las variables de una fórmula booleana determinada se pueden reemplazar consistentemente por los valores VERDADERO o FALSO de tal manera que la fórmula se evalúe como VERDADERO . Si este es … Continue reading «Prueba de que SAT es NP Completo»
Prerrequisitos: DFS , Trees , DSU Dado un árbol con N Nodes desde el valor 1 hasta N y E bordes y array arr[] que denota el número asociado a cada Node. También recibe consultas Q que contienen 2 enteros {V, F} . Para cada consulta, hay un subárbol con vértice V , la tarea … Continue reading «Unión de conjuntos disjuntos extendidos en árboles»
Dada la string str , la tarea es contar todas las substrings de str que son palíndromos y su longitud es prima. Ejemplos: Entrada: str = «geeksforgeeks» Salida: 2 «ee» y «ee» son las únicas substrings válidas. Entrada: str = “abccc” Salida: 3 Enfoque: utilizando la criba de Eratóstenes , encuentre todos los números primos … Continue reading «Cuente todas las substrings palindrómicas de longitud principal»
¿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»
Dada una string S y una array Q de consultas, cada una especificando los índices inicial y final L( = Q[i][0]) y R( = Q[i][0]) respectivamente de una substring de S, la tarea es encontrar la frecuencia de la string K en la substring [L, R] . Nota: Los rangos siguen la indexación basada en … Continue reading «Consultas para encontrar frecuencias de una string dentro de substrings especificadas»
Dado que N personas están sentadas en una cola circular numerada del 1 al N , la tarea es contar el número de formas de seleccionar un subconjunto de ellas de modo que no haya dos personas consecutivas sentadas juntas. La respuesta podría ser grande, así que calcula la respuesta módulo 10 9 + 7 … Continue reading «Cuente subconjuntos no adyacentes a partir de números dispuestos en forma circular»
Los números de Fibonacci son los números en la siguiente secuencia de enteros 0, 1, 1, 2, 3, 5, 8, 13… Matemáticamente, los números de Fibonacci se pueden escribir mediante la siguiente fórmula recursiva. For seed values F(0) = 0 and F(1) = 1 F(n) = F(n-1) + F(n-2) Antes de continuar con este artículo, … Continue reading «Complejidad temporal del programa recursivo de Fibonacci»
Dada una array binaria. En una sola operación, puede elegir dos elementos adyacentes e invertir su paridad. La operación se puede realizar cualquier número de veces. Escriba un programa para verificar si todos los elementos de la array se pueden convertir en una sola paridad. Ejemplos: Entrada: a[] = {1, 0, 1, 1, 0, 1} Salida: … Continue reading «Compruebe si todos los elementos se pueden hacer de la misma paridad invirtiendo elementos adyacentes»