Categoría: Analysis

Método eficiente para almacenar una array triangular inferior utilizando el mapeo de columnas principales

Posted on by Rudeus Greyrat

Dada una array triangular inferior Mat[][] , la tarea es almacenar la array utilizando el mapeo de columnas principales . Array triangular inferior: una array triangular inferior es una array cuadrada en la que la parte triangular inferior de una array consta de elementos distintos de cero y la parte triangular superior consta de 0 … Continue reading «Método eficiente para almacenar una array triangular inferior utilizando el mapeo de columnas principales»

Análisis de Algoritmos | Notación Big – Θ (Big Theta)

Posted on by Rudeus Greyrat

En el análisis de algoritmos , las notaciones asintóticas se utilizan para evaluar el rendimiento de un algoritmo, en sus mejores y peores casos . Este artículo discutirá las notaciones Big – Theta representadas por una letra griega (Θ). Definición: Sean g y f la función del conjunto de los números naturales a sí mismo. … Continue reading «Análisis de Algoritmos | Notación Big – Θ (Big Theta)»

¿Por qué falla el algoritmo de Dijkstra en pesos negativos?

Posted on by Rudeus Greyrat

Algoritmo de Dijkstra : es un algoritmo de búsqueda de gráficos que utiliza un enfoque codicioso para encontrar la ruta más corta desde el Node de origen hasta todos los demás Nodes restantes . Resuelve el problema de la ruta más corta de fuente única para un gráfico ponderado. Este algoritmo realiza un seguimiento de … Continue reading «¿Por qué falla el algoritmo de Dijkstra en pesos negativos?»

Prueba de que el conjunto dominante de un gráfico es NP-completo

Posted on by Rudeus Greyrat

Prerrequisito: Conjunto Dominante de un Gráfico , NP-Completo Un conjunto dominante en un grafo G = (V, E) es un subconjunto de vértices V’ siguiendo la condición de que los vértices que no pertenecen a V’ sean adyacentes a algún vértice en V’ . Problema: Dado un grafo G(V, E) y un entero k, el … Continue reading «Prueba de que el conjunto dominante de un gráfico es NP-completo»

Compruebe si la string sigue siendo palíndromo después de eliminar el número dado de caracteres

Posted on by Rudeus Greyrat

Dada una string palindrómica str y un entero N . La tarea es encontrar si es posible eliminar exactamente N caracteres de la string dada de modo que la string siga siendo un palíndromo. Ejemplos:   Entrada: str = “abba”, N = 1  Salida: Sí  Quite ‘b’ y la string remanente  “aba” sigue siendo un palíndromo. … Continue reading «Compruebe si la string sigue siendo palíndromo después de eliminar el número dado de caracteres»

Maximizar la suma del tercer elemento en conjuntos de cuatrillizos formados a partir de una array dada

Posted on by Rudeus Greyrat

Dada una array arr que contiene N valores que describen la prioridad de N trabajos. La tarea es formar conjuntos de cuatrillizos (W, X, Y, Z) que se realizarán cada día de manera que W >= X >= Y >= Z y, al hacerlo, maximizar la suma de todos los Y en todos los conjuntos … Continue reading «Maximizar la suma del tercer elemento en conjuntos de cuatrillizos formados a partir de una array dada»

Tiempo Complejidad de construir un montón

Posted on by Rudeus Greyrat

Considere el siguiente algoritmo para construir un Montón de una array de entrada A.  CONSTRUIR-MONTÓN (A)      heapsize := tamaño(A);      for i := floor(heapsize/2) downto 1          hacer HEAPIFY(A, i);      fin para  FINAL Una mirada rápida al algoritmo anterior sugiere que el tiempo de ejecución es   desde … Continue reading «Tiempo Complejidad de construir un montón»

Suma máxima obtenida al dividir Array en varios subarreglos según las condiciones dadas

Posted on by Rudeus Greyrat

Dado un arreglo arr[] de tamaño N , la tarea es calcular la suma máxima que se puede obtener al dividir el arreglo en varios subarreglos ( posiblemente uno), donde cada subarreglo comienza en el índice i y termina en el índice j (j>= i) contribuye arr[j]-arr[i] a la suma. Ejemplos: Entrada: arr[]= {1, 5, … Continue reading «Suma máxima obtenida al dividir Array en varios subarreglos según las condiciones dadas»

Podar y buscar | Una descripción general del análisis de complejidad

Posted on by Rudeus Greyrat

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»

Longitud máxima del subarreglo tal que la suma del subarreglo sea par

Posted on by Rudeus Greyrat

Dada una array de N elementos. La tarea es encontrar la longitud del subarreglo más largo tal que la suma del subarreglo sea par. Ejemplos:   Input : N = 6, arr[] = {1, 2, 3, 2, 1, 4} Output : 5 Explanation: In the example the subarray in range [2, 6] has sum 12 which … Continue reading «Longitud máxima del subarreglo tal que la suma del subarreglo sea par»