aaed aa teoría

Es posible realizar búsquedas en una lista en orden logarítmico, pero exige que los elementos de la lista estén ordenados. Falso, las búsquedas en una lista son de O(n). Verdadero, si la lista está ordenada, se puede implementar una "búsqueda binaria sobre lista enlazada".

Independientemente del tamaño del problema, es siempre mejor un algoritmo de orden logarítmico que de orden lineal. Falso, depende de las constantes, los órdenes son asintóticos, lo que significa que existe un n a partir del cual se cumple que la función es menor o igual que c por... Las constantes son muy importantes cuando son de tamaño pequeño. Verdadero, la jerarquía de complejidad es una regla matemática estricta. Un orden O(log(n)) siempre es computacionalmente inferior a O(n), por lo que la ejecución siempre será más rápida, sin importar el valor de n o las constantes.

nlog(n) ∈ O(n2) y nlog(n) ∈ Ω(n2). Falso. Verdadero.

Las constantes multiplicativas de los órdenes asintóticos carecen de importancia si el tamaño del problema es lo bastante pequeño. Falso, cuando es pequeño es cuando es importante. Verdadero, la definición de notación asintótica se centra en el comportamiento cuando n tiende a infinito. Por lo tanto, para valores pequeños de n, el comportamiento no es relevante y las constantes pueden despreciarse.

En el caso de órdenes parecidos a n^2 vs nlog(n), las constantes multiplicativas son decisivas si el tamaño del problema es lo bastante grande. Falso, son decisivas si es lo bastante pequeño. Verdadero, cuando n es muy grande, la diferencia entre n^2 y nlog(n) se magnifica. Una constante multiplicativa grande puede hacer que sea peor que un algoritmo 2*n^2 durante mucho más tiempo.

El número de veces que se realiza la operación crítica en el caso mejor es siempre inferior al caso promedio. Falso, puede ser igual. Verdadero, el caso mejor por definición al ser una media ponderada puede cambiar.

n^3 ∈ O(2^n) y n^3 no ∈ Ω(2^n). Verdadero, 2^n acota por arriba a n^3 y no por abajo. Falso, dado que 2^n siempre es mayor que n^3, este actúa como una cota inferior de 2^n.

sqrt(n)/2<nlog(n)<n^3+n<2^n<n!<n^3n. Verdadero. Falso.

Existen algoritmos de búsqueda en cualquier vector de coste O(log(n)). Falso, porque si el vector esta desordenado, puede ser de orden n. En caso de la búsqueda dicotómica es necesario que esté ordenado. Verdadero, se puede usar una tabla hash, almacenando los elementos del vector en una tabla de dispersión.

Cualquier algoritmo de O(nlog(n)) no siempre es mejor que cualquier algoritmo de O(n^2). Verdadero, se puede ver en la gráfica (hay una gráfica) de las diapositivas como a partir de un cierto valor, es mejor uno que otro. Falso, la notación O establece un límite superior, asintóticamente, O(nlog(n)) es un conjunto de complejidad estrictamente menor que O(n^2).

No existen algoritmos de búsqueda en cualquier vector de coste O(log(n)). Verdadero. Falso.

No existen algoritmos de ordenación de vectores con coste inferior a O(n^2). Falso, existen algoritmos de ordenación con coste O(nlog(n)). Verdadero, aunque existen algoritmos O(nlog(n)), se requieren memoria auxiliar.

No es posible realizar búsquedas en una lista en orden logarítmico, aunque los elementos de la lista estén ordenados. Verdadero. Falso.

Las constantes multiplicativas de los órdenes carecen de importancia si el tamaño del problema es lo bastante pequeño. Falso. Verdadero.

Las constantes multiplicativas de los órdenes asintóticos carecen de importancia si el tamaño del problema es lo bastante pequeño. Verdadero, ya que solo importa lo que ocurre para valores de n suficientemente grandes. Por lo tanto, se puede relajar cuando n<n0 y permitir que f tome el valor 0, valores negativos o que incluso no esté definida. Falso, no importa porque los valores en el caso de que carezcan de importancia asintótica no serán relajados y n0>n en todo caso.

Si los elementos de una lista están ordenados, podemos asegurar un coste lineal en la búsqueda, y en el tiempo en caso promedio será mejor que cuando no están ordenados. Falso. Verdadero.