AAED Examen Final (Teoría Análisis de Algoritmos)

¿Qué diferencia fundamental hay entre problema, algoritmo y programa?. El problema define qué se quiere resolver; el algoritmo cómo resolverlo de forma abstracta; el programa cómo implementarlo en una máquina real. El problema describe el lenguaje; el algoritmo la máquina; el programa el resultado final. El algoritmo define el problema; el programa es una versión informal del algoritmo. Problema y algoritmo son equivalentes; el programa solo añade sintaxis.

¿Cómo se define formalmente un problema en este contexto?. Como una función que transforma entradas en salidas. Como un conjunto de instrucciones ejecutables en una máquina. Como una secuencia finita de pasos ordenados. Como un programa independiente del lenguaje.

¿Qué caracteriza a un algoritmo frente a un programa?. Es abstracto, independiente de lenguaje y máquina, y consiste en una secuencia finita de instrucciones. Está escrito en un lenguaje concreto y se ejecuta directamente. Depende de la arquitectura hardware utilizada. Solo puede expresarse mediante código fuente compilable.

¿Por qué un programa depende necesariamente de un algoritmo correcto y eficiente?. Porque un programa hereda la corrección y eficiencia del algoritmo que implementa. Porque el compilador optimiza automáticamente cualquier programa. Porque la eficiencia depende solo del lenguaje de programación. Porque la máquina garantiza resultados correctos si el programa termina.

¿Para qué se utiliza el Lenguaje de Especificación de Algoritmos (LEA)?. Para describir algoritmos de forma concisa, abstracta y con semántica bien definida. Para programar algoritmos directamente en código ejecutable. Para medir el tiempo real de ejecución de un programa. Para optimizar algoritmos a bajo nivel.

¿Qué tipos de construcciones básicas permite LEA?. Asignación (normal y paralela), condición e iteración. Clases, objetos y herencia. Funciones recursivas y estructuras dinámicas. Entrada/salida y manejo de memoria.

¿Por qué LEA es preferible a lenguajes informales para describir algoritmos?. Porque evita ambigüedades y define claramente el significado de cada instrucción. Porque es más cercano a los lenguajes de programación reales. Porque permite ejecutar directamente los algoritmos. Porque reduce el número de instrucciones necesarias.

¿Qué preguntas responde la corrección algorítmica?. Si el algoritmo termina y si, cuando termina, produce el resultado correcto. Cuánto tiempo tarda en ejecutarse en una máquina concreta. Qué lenguaje es más eficiente para implementarlo. Cuánta memoria ocupa el programa final.

¿Qué diferencia hay entre parada y corrección parcial?. La parada asegura que el algoritmo termina; la corrección parcial que el resultado es correcto si termina. La parada garantiza resultados correctos; la corrección parcial garantiza eficiencia. Ambas significan exactamente lo mismo. La corrección parcial analiza el tiempo y la parada el espacio.

¿Qué recursos se analizan principalmente en la eficiencia algorítmica?. Tiempo y espacio, a nivel abstracto. Tiempo real de ejecución y consumo eléctrico. Número de líneas de código y lenguaje usado. Velocidad del procesador y memoria física.

¿Por qué el análisis se hace sobre algoritmos y no solo sobre programas?. Porque el comportamiento esencial no depende del lenguaje ni de la máquina concreta. Porque los programas no pueden analizarse formalmente. Porque los algoritmos siempre son más rápidos que los programas. Porque el hardware elimina las diferencias de eficiencia.

¿Qué ilustra el ejemplo de la multiplicación rusa?. La diferencia entre algoritmo abstracto y su implementación concreta en un programa. Una optimización específica de bajo nivel. Un caso donde programa y algoritmo coinciden exactamente. Una técnica dependiente del lenguaje de programación.

¿Por qué distintos programas pueden implementar el mismo algoritmo?. Porque el algoritmo es independiente del lenguaje y de la sintaxis concreta. Porque todos los lenguajes tienen la misma sintaxis. Porque el compilador unifica todos los programas. Porque los programas no afectan al resultado.

¿Qué afirma el principio de invarianza?. Que dos programas del mismo algoritmo sólo difieren en tiempo por un factor constante. Que todos los algoritmos tienen el mismo tiempo de ejecución. Que cambiar el lenguaje cambia el orden de eficiencia. Que el hardware no influye en absoluto.

¿Cuándo deja de cumplirse el principio de invarianza?. Si se cambia el algoritmo o se altera radicalmente la arquitectura de la máquina. Cuando se optimiza el código fuente. Cuando se usa otro compilador. Cuando el tamaño de entrada es pequeño.

¿Qué implicación tiene este principio para la optimización de programas?. Que las mejoras de bajo nivel no cambian el orden de eficiencia del algoritmo. Que optimizar el código siempre mejora el orden asintótico. Que la optimización elimina la necesidad de analizar algoritmos. Que solo importa el lenguaje usado.

¿Qué significa que dos algoritmos tengan el mismo orden?. Que sus tiempos de ejecución difieren solo por constantes multiplicativas. Que ejecutan exactamente el mismo número de instrucciones. Que producen los mismos resultados. Que usan el mismo lenguaje de programación.

¿Por qué esta definición se considera informal o imprecisa?. Porque requiere una formalización mediante tiempo algorítmico y orden asintótico. Porque no se puede medir el tiempo de ejecución. Porque depende del hardware concreto. Porque los algoritmos no pueden compararse.

¿Por qué se introduce el concepto de orden asintótico en el análisis de algoritmos?. Para comparar eficiencias ignorando constantes y detalles de implementación. Para medir el tiempo real de ejecución en una máquina concreta. Para optimizar programas a bajo nivel. Para contar exactamente el número de instrucciones ejecutadas.

¿Qué papel juega el principio de invarianza en el uso de órdenes asintóticos?. Justifica que solo importa el crecimiento del algoritmo, no la máquina ni el programa. Garantiza que todos los algoritmos tienen el mismo tiempo de ejecución. Permite ignorar completamente el tamaño de la entrada. Afirma que el lenguaje de programación no influye en la eficiencia real.

¿Cómo se relaciona la eficiencia de un algoritmo con el tamaño de la entrada?. Mediante funciones que asignan a cada tamaño un consumo de recursos. Mediante el tiempo real medido en segundos. Mediante el número de líneas de código. Mediante la velocidad del procesador utilizado.

¿Qué expresa intuitivamente que un algoritmo sea O(f(n))?. Que su tiempo crece, como máximo, proporcionalmente a f(n). Que su tiempo crece exactamente como f(n). Que su tiempo nunca supera un valor constante. Que su tiempo depende del peor programa posible.

¿Qué significa que la definición de O sea asintótica?. Que solo importa el comportamiento para n suficientemente grande. Que se aplica solo a valores pequeños de n. Que tiene en cuenta constantes y detalles de implementación. Que describe el tiempo exacto de ejecución.

¿Por qué las constantes y los valores pequeños de n no son relevantes en O?. Porque quedan absorbidos por los multiplicadores y el umbral n₀. Porque no pueden medirse con precisión. Porque siempre son despreciables en cualquier caso. Porque solo se analizan entradas unitarias.

¿Qué relación existe entre pertenencia f ∈ O(g) y contención de conjuntos?. f ∈ O(g) equivale a O(f) ⊆ O(g). f ∈ O(g) implica que f = g. O(g) ⊆ O(f) siempre que f ∈ O(g). No existe relación formal entre ambas.

¿Qué tipo de relación induce O entre funciones de coste?. Un preorden reflexivo y transitivo, pero no total. Una relación de equivalencia. Un orden total estricto. Una relación antisimétrica y total.

¿Por qué multiplicar por una constante no cambia el orden asintótico?. Porque las constantes quedan absorbidas en la definición de O. Porque las constantes siempre valen 1. Porque el tiempo real no depende de constantes. Porque el compilador elimina las constantes.

¿Por qué O(f + g) se simplifica como O(max{f, g})?. Porque el término dominante controla el crecimiento. Porque siempre se pueden sumar las funciones. Porque f y g crecen al mismo ritmo. Porque max{f, g} es siempre mayor que f + g.

¿Cómo se puede comparar el orden de dos funciones usando límites?. Analizando el límite del cociente f(n)/g(n). Comparando sus valores para n = 1. Midiendo el tiempo de ejecución real. Sumando ambas funciones.

¿Qué idea transmite la jerarquía de complejidad entre funciones?. Que algunos crecimientos son inherentemente mucho más rápidos que otros. Que todas las funciones pueden optimizarse al mismo nivel. Que la eficiencia depende solo del hardware. Que las funciones polinómicas y exponenciales son equivalentes.

¿Por qué los algoritmos exponenciales son impracticables para n grandes?. Porque su tiempo crece demasiado rápido incluso con pequeñas entradas. Porque no pueden implementarse en lenguajes reales. Porque consumen siempre memoria infinita. Porque solo funcionan para n pequeño por definición.

¿Qué nos enseñan las tablas sobre duplicar tiempo o tamaño de entrada?. Que el impacto depende críticamente del orden asintótico del algoritmo. Que duplicar la entrada siempre duplica el tiempo. Que el tiempo real es impredecible. Que el hardware elimina las diferencias.

¿Qué expresa intuitivamente que un algoritmo sea Ω(f(n))?. Que su tiempo crece al menos proporcionalmente a f(n). Que su tiempo crece como máximo f(n). Que su tiempo es exactamente f(n). Que su tiempo no depende de n.

¿Qué relación de dualidad existe entre O y Ω?. f ∈ O(g) si y solo si g ∈ Ω(f). O y Ω son equivalentes siempre. Ω es un subconjunto de O. No existe relación formal entre ambas.

¿Qué significa que un algoritmo sea Θ(f(n))?. Que su tiempo está acotado superior e inferiormente por f(n). Que su tiempo es menor que f(n). Que su tiempo es mayor que f(n). Que su tiempo depende del lenguaje usado.

¿Cómo se relacionan Θ, O y Ω entre sí?. Θ(f) = O(f) ∩ Ω(f). Θ(f) = O(f) ∪ Ω(f). O(f) = Θ(f) ∪ Ω(f). Ω(f) = O(f) − Θ(f).

¿Qué tipo de relación induce Θ entre funciones?. Una relación de equivalencia: mismo orden de crecimiento. Un orden total. Un preorden parcial. Una relación antisimétrica.

¿Qué significa operar órdenes asintóticos (suma o producto)?. Combinar funciones representativas de cada orden de forma consistente. Sumar tiempos reales de ejecución. Mezclar algoritmos distintos. Calcular el tiempo exacto del programa.

¿Por qué O(f) + O(g) = O(f + g) y O(f) · O(g) = O(f·g)?. Porque las operaciones se trasladan al crecimiento dominante. Porque siempre se suman y multiplican constantes. Porque O elimina cualquier término no lineal. Porque f y g siempre son comparables.

¿Qué significa comparar la eficiencia de algoritmos?. Comparar cuántos recursos computacionales consumen para resolver el mismo problema. Comparar el número de líneas de código de cada algoritmo. Comparar el tiempo real de ejecución en una máquina concreta. Comparar el lenguaje de programación utilizado.

¿Cuáles son los recursos fundamentales en una máquina secuencial?. Tiempo y espacio. Tiempo y energía. Memoria y velocidad del procesador. Entrada y salida.

¿Por qué los recursos de los algoritmos se consideran abstractos?. Porque no dependen de una máquina ni de una implementación concreta. Porque no pueden medirse en la práctica. Porque siempre son constantes. Porque solo se analizan programas teóricos.

¿Por qué se relaciona el uso de recursos con el tamaño de la entrada y no con la entrada concreta?. Porque analizar todas las entradas individuales es inviable. Porque todas las entradas del mismo tamaño son iguales. Porque el tamaño determina el lenguaje usado. Porque las entradas concretas no afectan al tiempo.

¿De qué depende la definición del tamaño de una entrada?. De su representación interna (elementos, dígitos, etc.). Del valor concreto de los datos. Del algoritmo que se aplique. De la máquina donde se ejecuta.

¿En qué consiste el enfoque teórico del análisis temporal?. En calcular t(n) y estudiar su orden de crecimiento. En medir tiempos reales de ejecución. En contar instrucciones de máquina. En optimizar el código fuente.

¿Qué caracteriza al enfoque empírico?. Mide tiempos reales de programas ejecutados. Analiza funciones de coste abstractas. Ignora la implementación concreta. Estudia solo el caso peor.

¿Qué ventaja aporta el enfoque híbrido?. Combina modelo teórico y medidas reales para ajustarlo. Elimina la necesidad de análisis matemático. Garantiza tiempos exactos. Solo se basa en pruebas experimentales.

¿Qué es una operación elemental?. Una operación que se ejecuta en tiempo constante Θ(1). Una operación que domina el tiempo total. Una instrucción de alto nivel. Una operación que depende del tamaño de la entrada.

¿Qué es una operación crítica?. La operación cuyo número de ejecuciones domina el tiempo total. La operación más compleja del algoritmo. La primera operación que se ejecuta. Una operación que siempre es Θ(1).

¿Por qué centrarse en una operación crítica simplifica el análisis?. Porque su número de ejecuciones determina el orden del algoritmo. Porque elimina la necesidad de contar otras operaciones. Porque siempre es la más lenta. Porque depende del hardware.

¿Cuándo el número de ejecuciones de la operación crítica refleja el tiempo real del programa?. Cuando la operación crítica es elemental. Cuando el programa está optimizado. Cuando se ejecuta en una máquina rápida. Cuando hay pocas instrucciones.

¿Por qué el tiempo puede variar para entradas del mismo tamaño?. Porque distintas entradas provocan ejecuciones diferentes. Porque el tamaño no influye realmente. Porque el algoritmo cambia. Porque el compilador optimiza distinto cada vez.

¿Cómo se define el caso peor para un tamaño n?. Como el máximo tiempo entre todas las entradas de tamaño n. Como el tiempo medio de ejecución. Como el tiempo de la entrada más frecuente. Como el mínimo tiempo posible.

¿Cómo se define el caso mejor para un tamaño n?. Como el mínimo tiempo entre todas las entradas de tamaño n. Como el tiempo promedio. Como el tiempo más habitual. Como el tiempo máximo posible.

¿Por qué suele analizarse principalmente el caso peor?. Porque proporciona una cota garantizada del comportamiento. Porque es el más frecuente. Porque es más fácil de medir empíricamente. Porque coincide con el caso promedio.

¿Cuándo tiene sentido estudiar el caso promedio?. Cuando hay diferencias significativas entre mejor y peor caso. Siempre, independientemente del algoritmo. Solo cuando el caso peor no existe. Cuando el algoritmo es determinista.

¿Qué relación existe entre caso mejor, promedio y peor?. tmín(n) ≤ t(n) ≤ tmáx(n). tmáx(n) ≤ t(n) ≤ tmín(n). t(n) = tmín(n) = tmáx(n). No existe relación formal.

¿Cuál es el procedimiento general para calcular t(n)?. Contar cuántas veces se ejecuta la operación crítica. Medir tiempos reales de ejecución. Contar todas las instrucciones del programa. Analizar el código fuente línea a línea.

¿Cómo se calcula el tiempo en una composición secuencial?. Sumando los tiempos de cada componente. Multiplicando los tiempos parciales. Tomando el máximo de los tiempos. Ignorando el primer componente.

¿Cómo se calcula el tiempo de una estructura condicional en el caso peor?. Sumando la condición y el máximo de las ramas. Sumando todas las ramas posibles. Tomando el promedio de las ramas. Ignorando la condición.

¿Cómo se analiza una estructura iterativa?. Contando el número de iteraciones y el coste de cada una. Midiendo el tiempo real de ejecución. Analizando solo una iteración. Ignorando el cuerpo del bucle.

¿Por qué el algoritmo de mínimo de un vector tiene t(n) ∈ Θ(n)?. Porque realiza siempre n−1 comparaciones, independientemente del contenido. Porque solo compara el primer elemento. Porque depende del orden del vector. Porque usa recursión.

¿Por qué la inserción en orden tiene mejor caso Θ(1)?. Porque puede detenerse tras la primera comparación. Porque no realiza comparaciones. Porque siempre recorre todo el vector. Porque depende del tamaño máximo.

¿Por qué el peor caso de la inserción en orden es Θ(n)?. Porque puede requerir desplazar el elemento a lo largo de todo el vector. Porque nunca desplaza elementos. Porque solo compara una vez. Porque el vector ya está ordenado.

¿Por qué el caso promedio de la inserción en orden sigue siendo Θ(n)?. Porque el número esperado de comparaciones crece linealmente. Porque siempre se da el peor caso. Porque el mejor caso es dominante. Porque el algoritmo es recursivo.

¿Qué efecto tienen las optimizaciones finales del algoritmo de inserción?. Reducen constantes, pero no cambian el orden asintótico. Cambian el orden de Θ(n) a Θ(1). Eliminan el peor caso. Hacen innecesario el análisis.

¿Cuál es el problema que resuelve la búsqueda secuencial?. Encontrar la primera posición de un elemento en un vector o indicar que no está. Ordenar un vector mediante comparaciones sucesivas. Insertar un elemento en su posición correcta. Encontrar el elemento central de un vector.

¿Cuál es la operación crítica en la búsqueda secuencial?. Las comparaciones entre el elemento buscado y los elementos del vector. Los intercambios de elementos adyacentes. Las asignaciones de memoria. El cálculo del tamaño del vector.

¿Por qué la búsqueda secuencial presenta distintos casos de complejidad?. Porque el número de comparaciones depende de la posición final del elemento. Porque el algoritmo cambia según el lenguaje. Porque depende del tamaño máximo del vector. Porque siempre se recorren todos los elementos.

¿Cuál es el mejor caso de la búsqueda secuencial y su orden?. Encontrar el elemento en la primera posición; Θ(1). Encontrarlo en la última posición; Θ(n). No encontrarlo; Θ(n). Encontrarlo en una posición aleatoria; Θ(log n).

¿Cuál es el peor caso de la búsqueda secuencial y su orden?. Recorrer todo el vector (esté o no el elemento); Θ(n). Encontrar el elemento al inicio; Θ(1). Detenerse a mitad del vector; Θ(n/2). No realizar comparaciones; Θ(1).

¿Por qué el caso promedio de la búsqueda secuencial es Θ(n)?. Porque el número esperado de comparaciones crece linealmente con n. Porque siempre se da el peor caso. Porque depende solo del mejor caso. Porque el vector está ordenado.

¿Qué tienen en común los métodos directos de ordenación estudiados?. Son algoritmos de ordenación por comparación. Son algoritmos recursivos. Son algoritmos no deterministas. No comparan elementos entre sí.

¿Qué problema general resuelven los algoritmos de ordenación?. Reordenar un vector según un orden total dado. Buscar un elemento concreto en un vector. Eliminar duplicados de un conjunto. Dividir un vector en subvectores.

¿En qué idea se basa la ordenación por intercambio directo?. Intercambiar elementos adyacentes para hacer “burbujeo” del mayor o menor. Seleccionar el mínimo y colocarlo al inicio. Insertar cada elemento en su posición correcta. Dividir el vector en partes iguales.

¿Por qué no hay diferencia entre caso mejor, peor y promedio en este método?. Porque el número de comparaciones depende solo de n, no del contenido. Porque siempre se intercambian los mismos elementos. Porque el vector siempre está ordenado. Porque se detiene antes si el vector está ordenado.

¿Cuál es el orden temporal de la ordenación por intercambio directo?. Θ(n²). Θ(n). Θ(log n). Θ(n log n).

¿Cuál es la idea central de la ordenación por selección directa?. Seleccionar repetidamente el mínimo y colocarlo en su posición final. Intercambiar elementos adyacentes. Insertar cada elemento en la parte ordenada. Dividir el vector recursivamente.

¿Por qué su análisis temporal coincide con el del intercambio directo?. Porque realiza el mismo número de comparaciones independientemente del vector. Porque intercambia los mismos elementos. Porque depende del contenido del vector. Porque se detiene antes en el mejor caso.

¿Cuál es su orden temporal en cualquier caso?. Θ(n²). Θ(n). Θ(log n). Θ(n log n).

¿En qué consiste la ordenación por inserción directa?. Insertar cada elemento en su posición correcta dentro de la parte ya ordenada. Intercambiar elementos extremos. Seleccionar el máximo en cada paso. Reordenar el vector completo en cada iteración.

¿Cuál es el mejor caso de la ordenación por inserción directa y por qué?. Cuando el vector ya está ordenado; solo una comparación por inserción. Cuando el vector está invertido; no hay desplazamientos. Cuando el vector es aleatorio; se minimizan comparaciones. Cuando el vector tiene un solo elemento.

¿Cuál es el peor caso de la ordenación por inserción directa y por qué?. Cuando el vector está en orden inverso; cada inserción recorre toda la parte ordenada. Cuando el vector está ordenado; no hay desplazamientos. Cuando el vector es pequeño; hay más comparaciones. Cuando el vector tiene duplicados.

¿Cuál es el orden del mejor y peor caso de la inserción directa?. Mejor: Θ(n); peor: Θ(n²). Mejor: Θ(1); peor: Θ(n). Mejor: Θ(log n); peor: Θ(n log n). Mejor: Θ(n²); peor: Θ(n).

¿Por qué el caso promedio de la inserción directa sigue siendo Θ(n²)?. Porque el número esperado de desplazamientos crece cuadráticamente. Porque siempre se da el peor caso. Porque el mejor caso domina. Porque no hay comparaciones.

¿Qué mide el número de inversiones de una permutación?. El grado de desorden del vector. El número de elementos repetidos. El tamaño del vector. El número de intercambios realizados.

¿Por qué los algoritmos directos tienen un límite inferior cuadrático?. Porque cada comparación elimina como máximo una inversión. Porque siempre recorren todo el vector. Porque no usan recursión. Porque dependen del hardware.

¿Qué afirma el teorema sobre algoritmos directos de ordenación?. Que requieren al menos Θ(n²) comparaciones en el peor y promedio caso. Que siempre pueden optimizarse a Θ(n log n). Que solo funcionan para vectores pequeños. Que no comparan elementos.

¿Por qué se introducen algoritmos de ordenación no directos?. Para superar las limitaciones de los métodos directos. Para simplificar la implementación. Para evitar comparaciones. Para reducir el uso de memoria únicamente.

¿Qué algoritmos no directos se relacionan con los métodos vistos?. Rápido (intercambio), montículo (selección) y Shell (inserción). Burbuja, selección e inserción. Secuencial, binaria y hash. Merge, radix y bucket.

¿Qué mide exactamente el análisis asintótico de un algoritmo y qué aspectos no pretende medir?. Mide la tasa de crecimiento del tiempo/espacio; no mide tiempo real ni constantes exactas. Mide el tiempo real de ejecución en una máquina concreta y el uso exacto de memoria. Mide el número total de instrucciones del programa compilado. Mide el rendimiento práctico incluyendo optimizaciones del compilador.

¿Qué representan formalmente O, Ω y Θ en el análisis de algoritmos y cómo se relacionan entre sí?. O es cota superior, Ω cota inferior, Θ cota ajustada; O y Ω son duales. O es el peor caso, Ω el mejor caso y Θ el caso medio. O y Θ son equivalentes y Ω no se usa en la práctica. O mide tiempo real, Ω espacio y Θ eficiencia media.

¿Por qué las constantes multiplicativas solo son relevantes cuando el tamaño del problema es pequeño?. Porque para n grande domina el orden asintótico y las constantes se vuelven despreciables. Porque las constantes solo afectan al mejor caso. Porque las constantes se eliminan al compilar el programa. Porque el análisis asintótico ignora siempre el tamaño del problema.

¿Cómo se definen los casos mejor, peor y promedio en el análisis temporal de un algoritmo?. Mejor = mínimo, peor = máximo, promedio = valor esperado; no es la media aritmética. Mejor = más frecuente, peor = menos frecuente, promedio = media aritmética. Mejor = caso ideal, peor = caso imposible, promedio = caso típico. Mejor = Θ(1), peor = Θ(n), promedio = Θ(log n).

¿Qué es la operación crítica y por qué es clave para calcular la complejidad temporal?. Es la operación dominante; su conteo determina la complejidad temporal. Es la operación más costosa en tiempo real. Es la primera instrucción del algoritmo. Es la operación que usa más memoria.

¿En qué condiciones estructurales puede realizarse una búsqueda en tiempo O(log n) y cuándo no es posible?. Solo con acceso aleatorio y datos ordenados; no en listas enlazadas. Siempre que los datos estén ordenados, independientemente de la estructura. En cualquier estructura que permita recorridos secuenciales. Únicamente cuando se usa recursión.

¿Por qué un algoritmo con mejor orden asintótico puede ser más lento en la práctica para ciertos tamaños?. Por constantes y sobrecostes que dominan en tamaños pequeños. Porque el orden asintótico solo se aplica al peor caso. Porque el compilador puede empeorar su rendimiento. Porque usa más memoria auxiliar.

¿Qué establece el principio de invarianza respecto a distintos programas que implementan el mismo algoritmo?. Que distintos programas del mismo algoritmo tienen la misma eficiencia asintótica (salvo constantes). Que todos los programas se ejecutan en el mismo tiempo. Que la implementación no influye nunca en el rendimiento. Que el lenguaje de programación determina el orden asintótico.

¿Por qué dos algoritmos con el mismo orden asintótico no realizan necesariamente el mismo número de operaciones?. Porque el orden describe crecimiento, no el número exacto de operaciones. Porque el análisis asintótico es aproximado y poco preciso. Porque uno puede usar más memoria que otro. Porque las constantes nunca influyen.

¿Cuál es la jerarquía correcta de crecimiento asintótico de las funciones más habituales?. constantes < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < n^{3n}. constantes < n < log n < n² < n log n < 2ⁿ < n!. log n < constantes < n < √n < n² < n log n < 2ⁿ. n < log n < constantes < √n < n log n < n².

¿Cuál es la complejidad temporal de la búsqueda binaria en el peor caso y cuál es la razón estructural?. O(log n), porque divide el problema a la mitad en cada paso. O(n), porque recorre todos los elementos. O(n log n), porque combina división y comparación. O(1), porque siempre accede al elemento central.

¿Cómo se modela y analiza el tiempo de ejecución de algoritmos recursivos?. Mediante ecuaciones de recurrencia del tipo T(n) = aT(n/b) + f(n). Contando directamente las llamadas recursivas. Usando únicamente notación Θ. Midiendo el tiempo real de ejecución.

¿Por qué existen algoritmos de ordenación con complejidad mejor que O(n²)?. Porque comparaciones y división permiten alcanzar O(n log n). Porque utilizan memoria adicional. Porque evitan completamente las comparaciones. Porque se ejecutan en paralelo.