Categoría: Analysis

Análisis de Algoritmos | Conjunto 4 (Análisis de bucles) – Part 1

Posted on by Rudeus Greyrat

Hemos discutido el análisis asintótico ,  los casos peor, promedio y mejor y las notaciones asintóticas en publicaciones anteriores. En este post, se discute un análisis de programas iterativos con ejemplos simples.  1) O(1): la complejidad de tiempo de una función (o conjunto de declaraciones) se considera como O(1) si no contiene bucle, recursividad ni … Continue reading «Análisis de Algoritmos | Conjunto 4 (Análisis de bucles) – Part 1»

Condición invariante de bucle con ejemplos

Posted on by Rudeus Greyrat

Definición: Una invariante de bucle es una condición [entre las variables de programa] que necesariamente se cumple inmediatamente antes e inmediatamente después de cada iteración de un bucle. (Tenga en cuenta que esto no dice nada acerca de su verdad o falsedad en medio de una iteración). Un bucle invariante es un predicado (condición) que … Continue reading «Condición invariante de bucle con ejemplos»

Recuento de rutas en el árbol binario dado con AND bit a bit impar para consultas Q

Posted on by Rudeus Greyrat

Dado un número entero Q que representa el número de consultas y una array donde cada consulta tiene un número entero N . Nuestra tarea es iterar a través de cada consulta y encontrar el número de rutas tal que el AND bit a bit de todos los Nodes en esa ruta sea impar.  Un … Continue reading «Recuento de rutas en el árbol binario dado con AND bit a bit impar para consultas Q»

Encuentra el número de pares mágicos de hilo de longitud L

Posted on by Rudeus Greyrat

Un par de strings s y r se llaman mágicas si para cada índice i el carácter de s es menor que r , es decir , s[i] < r[i] . La tarea es contar el número de pares de strings posibles de longitud L. Dado que este valor puede ser grande, dé la respuesta … Continue reading «Encuentra el número de pares mágicos de hilo de longitud L»

Conteo de coordenadas integrales que se encuentran dentro de un cuadrado

Posted on by Rudeus Greyrat

Dadas las coordenadas inferior izquierda y superior derecha (x1, y1) y (x2, y2) de un cuadrado, la tarea es contar el número de coordenadas integrales que se encuentran estrictamente dentro del cuadrado. Ejemplos:   Entrada: x1 = 1, y1 = 1, x2 = 5, x3 = 5  Salida: 9  Explicación:  A continuación se muestra el cuadrado … Continue reading «Conteo de coordenadas integrales que se encuentran dentro de un cuadrado»

Verifique si el Triángulo de Pascal es posible con una capa completa usando números hasta N

Posted on by Rudeus Greyrat

Dado un número N , la tarea es determinar si es posible hacer el triángulo de Pascal con una capa completa usando el número total N entero si es posible imprimir Sí de lo contrario imprimir No. Nota: el triángulo de Pascal es una array triangular de los coeficientes binomiales. Las siguientes son las primeras … Continue reading «Verifique si el Triángulo de Pascal es posible con una capa completa usando números hasta N»

Elementos mínimos insertados en una array ordenada para formar una progresión aritmética

Posted on by Rudeus Greyrat

Dada una array ordenada arr[] , la tarea es encontrar los elementos mínimos necesarios para insertar en la array de modo que la array forme una Progresión aritmética . Ejemplos:   Entrada: arr[] = {1, 6, 8, 10, 14, 16}  Salida: 10  Explicación:  Los elementos mínimos necesarios para formar AP son 10.  Array transformada después de … Continue reading «Elementos mínimos insertados en una array ordenada para formar una progresión aritmética»

Longitud del subarreglo más largo en el que los elementos mayores que K son más que los elementos no mayores que K

Posted on by Rudeus Greyrat

Dada una array arr[] de longitud N . La tarea es encontrar la longitud del subarreglo más largo en el que los elementos mayores que un número dado K son más que los elementos que no son mayores que K. Ejemplos: Entrada: N = 5, K = 2, arr[]={ 1, 2, 3, 4, 1 }  … Continue reading «Longitud del subarreglo más largo en el que los elementos mayores que K son más que los elementos no mayores que K»

Recuento de bits conjuntos pares e impares con elemento de array después de XOR con K

Posted on by Rudeus Greyrat

Dada una array arr[] y un número K . La tarea es encontrar el recuento del elemento que tiene un número par e impar del conjunto de bits después de tomar XOR de K con cada elemento del arr[] dado . Ejemplos:   Entrada: arr[] = {4, 2, 15, 9, 8, 8}, K = 3  Salida: … Continue reading «Recuento de bits conjuntos pares e impares con elemento de array después de XOR con K»

Ejemplos de preguntas sobre algoritmos | Conjunto 3 | Análisis de orden de tiempo

Posted on by Rudeus Greyrat

Pregunta 1: ¿Cuál es el límite asintótico de T(n)? θ( n*log(n) ) θ( norte 2 ) θ( norte ) θ( n*log 2 (n) ) θ( n 2 *log 2 (n) ) Respuesta: 3 Explicación: Para encontrar los límites superior e inferior apropiados, un enfoque que primero viene a la mente es expandir la notación sigma … Continue reading «Ejemplos de preguntas sobre algoritmos | Conjunto 3 | Análisis de orden de tiempo»