Categoría: Analysis

Diferencia entre algoritmos deterministas y no deterministas

Posted on by Rudeus Greyrat

En el algoritmo determinista , para una entrada particular dada, la computadora siempre producirá la misma salida pasando por los mismos estados, pero en el caso del algoritmo no determinista , para la misma entrada, el compilador puede producir una salida diferente en diferentes ejecuciones. De hecho, los algoritmos no deterministas no pueden resolver el … Continue reading «Diferencia entre algoritmos deterministas y no deterministas»

Análisis de Algoritmo | Conjunto 4 (Resolución de recurrencias)

Posted on by Rudeus Greyrat

  En la publicación anterior, discutimos el análisis de bucles . Muchos algoritmos son recursivos. Cuando los analizamos, obtenemos una relación de recurrencia para la complejidad del tiempo. Obtenemos el tiempo de ejecución en una entrada de tamaño n en función de n y el tiempo de ejecución en entradas de tamaños más pequeños. Por … Continue reading «Análisis de Algoritmo | Conjunto 4 (Resolución de recurrencias)»

Complejidad de diferentes operaciones en árbol binario, árbol de búsqueda binaria y árbol AVL

Posted on by Rudeus Greyrat

En este artículo, discutiremos la complejidad de diferentes operaciones en árboles binarios, incluidos los árboles BST y AVL. Antes de comprender este artículo, debe tener una idea básica sobre: ​​árbol binario, árbol de búsqueda binaria y árbol AVL . Las operaciones principales en el árbol binario son: buscar, insertar y eliminar. Veremos la complejidad temporal … Continue reading «Complejidad de diferentes operaciones en árbol binario, árbol de búsqueda binaria y árbol AVL»

Algoritmo en línea – Part 1

Posted on by Rudeus Greyrat

Un algoritmo en línea es aquel que puede procesar su entrada pieza por pieza en forma serial, es decir, en el orden en que la entrada se alimenta al algoritmo, sin tener toda la entrada disponible desde el principio. Por el contrario, un algoritmo fuera de línea recibe todos los datos del problema desde el … Continue reading «Algoritmo en línea – Part 1»

Operaciones mínimas para hacer suma de elementos vecinos <= X

Posted on by Rudeus Greyrat

Dada una array arr[] de N elementos y un entero X , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que la suma de los elementos vecinos sea menor que el número dado X. En una sola operación, puede elegir un elemento arr[i] y disminuir su valor en 1 . Ejemplos:   … Continue reading «Operaciones mínimas para hacer suma de elementos vecinos <= X»

Encuentre el K-ésimo número más pequeño tal que A + B = A | B

Posted on by Rudeus Greyrat

Dados dos números A y K , la tarea es encontrar el K-ésimo entero positivo más pequeño B, tal que A + B = A | B , donde | denota el operador OR bit a bit. Ejemplos:  Input: A = 10, K = 3 Output: 5 Explanation: K = 1, 10 + 1 = … Continue reading «Encuentre el K-ésimo número más pequeño tal que A + B = A | B»

Longitud máxima Subsecuencia con alternancia de signo y Suma máxima

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño n que tiene enteros positivos y negativos excepto cero. La tarea es encontrar la subsecuencia con un signo alterno que tenga el tamaño máximo y la suma máxima, es decir, en una subsecuencia, el signo de cada elemento adyacente es opuesto, por ejemplo, si el primero es positivo, el … Continue reading «Longitud máxima Subsecuencia con alternancia de signo y Suma máxima»

Propiedades de las notaciones asintóticas

Posted on by Rudeus Greyrat

Prerrequisito: notaciones asintóticas Suponiendo que f(n), g(n) y h(n) sean funciones asintóticas, las definiciones matemáticas son: Si f(n) = Θ(g(n)) , entonces existen constantes positivas c1, c2, n0 tales que 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n) , para todo n ≥ n0 Si f(n) = O(g(n)) , entonces existen constantes positivas c, n0 tales … Continue reading «Propiedades de las notaciones asintóticas»

Número esperado de ensayos para obtener N caras consecutivas

Posted on by Rudeus Greyrat

Dado un número N. La tarea es encontrar el número esperado de veces que se debe lanzar una moneda para obtener N caras consecutivamente. Ejemplo:   Entrada: N = 2  Salida: 6 Entrada: N = 5  Salida: 62   Planteamiento:  La clave es observar que si vemos cruz entre cualquier N tirada consecutiva, se rompe la racha … Continue reading «Número esperado de ensayos para obtener N caras consecutivas»

Recuento de subarreglos de tamaño K que tienen al menos un par con diferencia absoluta divisible por K-1

Posted on by Rudeus Greyrat

Dado un arr[] que consta de N elementos, la tarea es contar todos los subarreglos de tamaño K que tengan al menos un par cuya diferencia absoluta sea divisible por K – 1 . Ejemplos:   Entrada: arr[] = {1, 5, 3, 2, 17, 18}, K = 4  Salida: 3  Explicación:  Los tres subarreglos de tamaño … Continue reading «Recuento de subarreglos de tamaño K que tienen al menos un par con diferencia absoluta divisible por K-1»