Requisito previo: NP-Completitud Problema NP: El conjunto de problemas NP cuyas soluciones son difíciles de encontrar pero fáciles de verificar y se resuelven mediante una máquina no determinista en tiempo polinomial. Problema NP-Difícil : Un problema X es NP-Difícil si hay un problema NP-Completo Y, tal que Y es reducible a X en tiempo polinomial. … Continue reading «Diferencia entre problema NP difícil y NP completo»
Es un hecho bien establecido que la ordenación por fusión se ejecuta más rápido que la ordenación por inserción. Usando el análisis asintótico, podemos probar que la clasificación por fusión se ejecuta en el tiempo O (nlogn) y la clasificación por inserción toma O (n ^ 2). Es obvio porque la ordenación por fusión utiliza … Continue reading «Análisis asintótico y comparación de algoritmos de clasificación.»
Requisito previo: notaciones asintóticas , propiedades de las notaciones asintóticas , análisis de algoritmos 1. Notación oh grande (O): Se define como límite superior y el límite superior en un algoritmo es la mayor cantidad de tiempo requerido (el peor caso de rendimiento). La notación oh grande se usa para describir el límite superior asintótico … Continue reading «Diferencia entre Big Oh, Big Omega y Big Theta»
Dada una lista enlazada individualmente que contiene N Nodes, la tarea es encontrar la suma y el producto de todos los Nodes de la lista cuyo valor de datos tiene una suma de dígitos pares. Ejemplos: Entrada: 15 -> 16 -> 8 -> 6 -> 13 Salida: Suma = 42 Producto = 9360 Explicación: La … Continue reading «Suma y producto de todos los Nodes de suma de dígitos pares de una lista enlazada simple»
Dado un gran número en forma de string str y un número K , la tarea es verificar si el número formado por la string str es divisible por K o no, donde K es una potencia de 2. Ejemplos: Entrada: str = “5426987513245621541524288”, num = 64 Salida: Sí Explicación: Dado que log 2 (64) … Continue reading «Comprobar si un número grande es divisible por un número que es una potencia de 2»
El análisis amortizado se refiere a la determinación del tiempo de ejecución promedio para una operación secuencial (no individual). Es diferente del análisis de casos promedio porque aquí no asumimos que los datos están organizados de manera promedio (no muy mala) como lo hacemos para el análisis de casos promedio para clasificación rápida . Es … Continue reading «Análisis amortizado por incremento en contador»
Dado un número entero N , la tarea es dividir los números del 1 al N en dos subconjuntos no vacíos de modo que la suma de los elementos del conjunto sea igual. Imprime el elemento en el subconjunto. Si no podemos formar ningún subconjunto, imprima -1 . Ejemplos: Entrada N = 4 Salida: El … Continue reading «Dividir números del 1 al N en dos subconjuntos de igual suma»
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»
Dado un número binario como una string str de longitud L . La tarea es encontrar el número mínimo de operaciones necesarias para que el número se convierta en 2 L -1 , que es una string que consta de solo 1 de longitud L . En cada operación, el número N puede ser reemplazado por … Continue reading «Se requieren operaciones mínimas dadas para convertir una string binaria dada a todos los 1»
Dos jugadores, el jugador 1 y el jugador 2, están jugando un juego en una secuencia numérica dada S donde el jugador 1 comienza primero y ambos juegan de manera óptima. La tarea es encontrar si el jugador 1 gana o pierde. Si gana, escriba «Sí», de lo contrario, escriba «No». Las reglas del juego son … Continue reading «Juego de dos jugadores en el que un jugador puede eliminar todas las apariciones de un número»