Algoritmos y Complejidad Computacional

<p>Multiplicar el número de instrucciones por su coste. (B)</p> Signup and view all the answers

<p>10^18 operaciones por segundo (D)</p> Signup and view all the answers

<p>El conjunto de funciones donde f(n) es una cota inferior no estricta para valores grandes de n. (A)</p> Signup and view all the answers

<p>f(n) ∈ O(g(n)) y f(n) ∈ Ω(g(n)) (D)</p> Signup and view all the answers

<p>Θ(f(n)) indica que se puede expresar f(n) solo en términos de su cota superior. (B)</p> Signup and view all the answers

<p>O(máx(f, g)) (A)</p> Signup and view all the answers

<p>f ∈ O(h) (C)</p> Signup and view all the answers

<p>3 (A)</p> Signup and view all the answers

<p>O(y) (C)</p> Signup and view all the answers

<p>O(n⁴) (C)</p> Signup and view all the answers

<p>n² log n es menor que n³ (A)</p> Signup and view all the answers

<p>O(n⁵) (D)</p> Signup and view all the answers

<p>n² + 5n es O de n³ (C), n³ es ⌦ de n² + 5n (D)</p> Signup and view all the answers

<p>O(log y) (C)</p> Signup and view all the answers

<p>g(n) = n³ (B)</p> Signup and view all the answers

<p>O(log n) (D)</p> Signup and view all the answers

<p>El tamaño del problema se multiplica por 4. (A)</p> Signup and view all the answers

<p>Ambos B y C (A)</p> Signup and view all the answers

<p>O(n log n) es menos eficiente que O(n^2). (C)</p> Signup and view all the answers

<p>Duplica el tamaño del problema que se resuelve. (A)</p> Signup and view all the answers

<p>Son capaces de resolver problemas grandes en un tiempo razonable. (A)</p> Signup and view all the answers

<p>2 horas. (D)</p> Signup and view all the answers

<p>O(2^n) (B)</p> Signup and view all the answers

<p>Devuelve false. (A)</p> Signup and view all the answers

<p>Indicar la posición donde se debe insertar el nuevo elemento. (A)</p> Signup and view all the answers

<p>Es un valor temporal que guarda el elemento que se está insertando. (A)</p> Signup and view all the answers

<p>O(n^2) (D)</p> Signup and view all the answers

<p>No se realiza ninguna acción y se devuelve false. (D)</p> Signup and view all the answers

<p>Se mueven los elementos a partir de esa posición hacia la derecha. (A)</p> Signup and view all the answers

<p>O(n log n) (B)</p> Signup and view all the answers

<p>Desplaza los elementos hacia la derecha para hacer espacio para 'nuevo'. (B)</p> Signup and view all the answers

<p>Si g1 está en O(f1) y g2 está en O(f2), entonces g1 · g2 está en O(f1 · f2). (D)</p> Signup and view all the answers

<p>Cuando el límite de f(n) dividido por g(n) tiende a 1. (D)</p> Signup and view all the answers

<p>f(n) es de orden más bajo que g(n). (B)</p> Signup and view all the answers

<p>g pertenece a O(f) y f a O(g). (B)</p> Signup and view all the answers

<p>f(n) está en O(g(n)) y g(n) también está en O(f(n)). (A)</p> Signup and view all the answers

<p>El coeficiente del término de mayor grado debe ser positivo. (B)</p> Signup and view all the answers

<p>f(n) también debe estar en Ω(g(n)). (A)</p> Signup and view all the answers

<p>f(n) y g(n) tienen el mismo orden de crecimiento. (A)</p> Signup and view all the answers

La eficiencia de un algoritmo se refiere a la cantidad de recursos (tiempo, memoria, etc.) que consume para resolver un problema. Medir la eficiencia nos permite comparar algoritmos que resuelven un mismo problema.

Una forma poco práctica de calcular la eficiencia de un algoritmo es contar las instrucciones y multiplicarlas por su costo. Cada instrucción tiene un tiempo asociado, como asignación, comparación, incremento/decremento o acceso a memoria.

El tiempo de ejecución de un algoritmo puede variar dependiendo de la entrada. Por ejemplo, si buscamos un valor en un vector, la eficiencia dependerá de la posición del valor dentro del vector.

Los algoritmos suelen ser evaluados en términos de su tiempo de crecimiento, que es una manera de describir cómo aumenta el tiempo de ejecución a medida que aumenta el tamaño de la entrada.

Las operaciones de un algoritmo son las instrucciones que se ejecutan para resolver un problema. Cada instrucción tiene un costo asociado.

Es un conjunto de funciones donde f(n) es una cota inferior para valores suficientemente grandes de n. Es decir, la función g(n) siempre será mayor o igual a cf(n) (c es una constante positiva) a partir de un cierto valor de n (n0).

Es el conjunto de funciones donde f(n) es una cota superior para valores suficientemente grandes de n. Es decir, la función g(n) siempre será menor o igual a cf(n) (c es una constante positiva) a partir de un cierto valor de n (n0).

Una función f(n) pertenece al orden exacto de g(n) si f(n) es tanto una cota superior como una cota inferior de g(n). Esto significa que ambas funciones crecen a la misma velocidad.

Es la clasificación de funciones en grupos de acuerdo a su velocidad de crecimiento. Cada grupo representa un orden de complejidad.

La notación O grande (O(f(n))) representa un conjunto de funciones que están acotadas superiormente por una función f(n) multiplicada por una constante positiva y aplicada a un valor suficientemente grande de n.

La notación Omega (⌦(f(n))) representa un conjunto de funciones que están acotadas inferiormente por una función f(n) multiplicada por una constante positiva y aplicada a un valor suficientemente grande de n.

La notación Theta (⇥(f(n))) representa un conjunto de funciones que crecen a la misma velocidad que f(n) multiplicada por una constante positiva a medida que n tiende al infinito.

Si g(n) 2 O(f(n)), entonces f(n) 2 ⌦(g(n)).

Si el límite de f(n)/g(n) es una constante positiva a medida que n tiende al infinito, entonces O(f(n)) = O(g(n)).

Si el límite de f(n)/g(n) es 0 a medida que n tiende al infinito, entonces O(f(n)) ⇢ O(g(n)).

Si el límite de f(n)/g(n) es infinito a medida que n tiende al infinito, entonces O(f(n)) O(g(n)).

Si una función h(n) está acotada superiormente por una constante multiplicada por la suma de dos funciones f(n) y g(n) para un valor suficientemente grande de n, entonces h(n) está en O(f(n) + g(n)).

El orden asintótico de un algoritmo describe cómo el tiempo de ejecución o el uso de memoria aumenta a medida que aumenta el tamaño de la entrada. Básicamente, te dice qué tan rápido crece la función que describe el tiempo o el espacio.

Un algoritmo es de complejidad O(n) si su tiempo de ejecución crece linealmente con el tamaño de la entrada (n). Por ejemplo, si un bucle recorre todos los elementos de un array, el tiempo de ejecución será proporcional a la cantidad de elementos en el array.

Un algoritmo es de complejidad O(n²) si su tiempo de ejecución crece cuadráticamente con el tamaño de la entrada (n). Por ejemplo, si un algoritmo compara cada elemento con todos los demás elementos de un array, el tiempo de ejecución será proporcional al cuadrado de la cantidad de elementos en el array.

Un algoritmo es de complejidad O(log n) si su tiempo de ejecución crece logarítmicamente con el tamaño de la entrada (n). Este tipo de algoritmos suelen dividir el problema en subproblemas más pequeños hasta que se resuelve el problema original. Por ejemplo, la búsqueda binaria tiene una complejidad logarítmica.

Un algoritmo es de complejidad O(1) si su tiempo de ejecución es constante, independientemente del tamaño de la entrada.

El caso peor de un algoritmo es el caso de la entrada más desafiante que puede recibir. Por ejemplo, en un algoritmo de búsqueda, el caso peor podría ser cuando el elemento que buscamos no está presente en el conjunto de datos.

El caso mejor de un algoritmo es el caso de la entrada más simple que puede recibir. Por ejemplo, en un algoritmo de búsqueda, el caso mejor podría ser cuando el elemento que buscamos está en el primer lugar del conjunto de datos.

El caso promedio de un algoritmo es el caso promedio de todas las entradas posibles. Es difícil de calcular exactamente, pero da una idea general de cómo funciona el algoritmo en una situación típica.

La función insertar inserta un elemento en una lista ordenada sin repeticiones. En el caso mejor, el nuevo elemento se inserta al final de la lista, por lo que solo se ejecuta la condición lista.cont == MAX y no se ejecuta el bucle. En el caso peor, el nuevo elemento se inserta al inicio de la lista, por lo que se ejecutan todas las instrucciones del bucle.

La función insertar utilizando búsqueda lineal recorre toda la lista buscando la posición donde se inserta el nuevo elemento. En el caso mejor, el elemento se encuentra en el último lugar de la lista, por lo que se ejecutan todas las instrucciones del bucle. En el caso peor, el elemento se encuentra en el primer lugar de la lista, por lo que se ejecutan todas las instrucciones del bucle.

La función insertar utilizando búsqueda binaria divide el espacio de búsqueda a la mitad en cada iteración. En el caso mejor, el elemento se encuentra en la mitad de la lista, por lo que se ejecutan solo las instrucciones del bucle para dividir la lista. En el caso peor, el elemento se encuentra en el último lugar de la lista, por lo que se ejecutan todas las instrucciones del bucle.

La función ordenar utiliza el algoritmo de inserción directa para ordenar una lista de enteros. En el caso mejor, la lista ya está ordenada, por lo que se ejecuta solo la condición del bucle exterior del algoritmo. En el caso peor, la lista está ordenada de forma inversa, por lo que se ejecutan todas las instrucciones del algoritmo.

La función ordenar utilizando el algoritmo de inserción directa recorre la lista elemento por elemento, comparando cada elemento con los elementos anteriores para ubicarlo en la posición correcta. En el caso mejor, la lista ya está ordenada, por lo que solo se ejecutarán las instrucciones del bucle exterior. En el caso peor, la lista está ordenada de forma inversa, por lo que se ejecutarán todas las instrucciones del algoritmo.

La función ordenar utiliza el algoritmo de la burbuja para ordenar una lista de enteros. En el caso mejor, la lista ya está ordenada, por lo que se ejecuta solo la condición del bucle exterior del algoritmo. En el caso peor, la lista está ordenada de forma inversa, por lo que se ejecutan todas las instrucciones del algoritmo.

La función ordenar utilizando la ordenación por burbuja recorre la lista varias veces, comparando pares de elementos adyacentes e intercambiándolos si están fuera de orden. En el caso mejor, la lista ya está ordenada, por lo que se ejecuta solo la condición del bucle exterior del algoritmo. En el caso peor, la lista está ordenada de forma inversa, por lo que se ejecutarán todas las instrucciones del algoritmo.

Cada iteración del bucle intercambia elementos adyacentes si están fuera de orden. En el caso mejor, solo se ejecuta una iteración del bucle exterior, ya que la lista está ordenada. En el caso peor, el número de iteraciones del bucle exterior será igual al número de elementos en la lista.

Una función que crece de manera logarítmica con respecto al tamaño de la entrada. Estas funciones se caracterizan por dividir el problema en partes mas pequeñas hasta resolverlo. Un ejemplo de una función logarítmica es "log10n".

Una función que crece linealmente con respecto al tamaño de la entrada. Se ejecuta una cantidad fija de operaciones por cada elemento de entrada. Un ejemplo de una función lineal es "n".

Una función que crece de manera cuadrática con respecto al tamaño de la entrada. El tiempo de ejecución aumenta exponencialmente con el tamaño de la entrada. Un ejemplo de una función cuadrática es "n2".

Una función que crece exponencialmente. El tiempo de ejecución aumenta increíblemente rápido a medida que aumenta la entrada. Un ejemplo de una función exponencial es "2n".

Una función que representa un tiempo de ejecución constante, independientemente del tamaño de la entrada. Se ejecuta una cantidad fija de operaciones. Un ejemplo de una función constante es "1".

Conjunto de funciones que están acotadas inferiormente por una función f(n) multiplicada por una constante, para valores suficientemente grandes de n.