En primer lugar, debe tener cuidado con la notación big-O. Debe saber que 1 = O (n ^ 2): un algoritmo constante también se ejecuta en O (n ^ 2). Así que creo que la notación correcta aquí es Theta (n ^ 2) u Omega (n ^ 2), cuando quieres hablar sobre algunas operaciones ejecutadas al menos tan lento como este TC.
En segundo lugar, debe solicitar aclaraciones: ¿qué operaciones admite la estructura de datos? ¿Qué es n? ¿Es ese el tamaño de la matriz (presunto), o el rango de los enteros que se almacenan? En ambos casos es posible diseñar dicha estructura de datos, creo que esto hará la diferencia.
Para el primer caso, supongamos que n es el tamaño de la matriz. Luego, debe solicitar una aclaración sobre las operaciones permitidas. Digamos, cualquier operación de recuperación. Puede definir una Lista vinculada, con tamaño n. Cuando inserta el i-ésimo elemento x, inserta i copias del mismo elemento x al final de la Lista vinculada. Recuerde que esta estructura de datos no recuerda el puntero final, por lo que cuando desea encontrar el final, debe recorrer toda la lista. Ahora, desea recuperar el último elemento, luego debe recorrer la lista completa, lo que requerirá 1 + 2 +… + n = Theta (n ^ 2) visitas en total. Tenga en cuenta que esta es la mejor complejidad de tiempo para la última operación de recuperación de elementos que desee.
Para el segundo caso, supongamos que n es la capacidad del número: cada entero está en el rango 1..n. En este caso, puede emplear una idea similar a la anterior. Inicialmente, el DS contiene una lista vinculada de n * n elementos: n elementos para cada i de 1 a n, vinculados en orden ascendente. Cuando se agrega un nuevo elemento, repite lo que estaba haciendo para el primer caso. Por otra parte, para recuperar cada elemento, primero debe atravesar los elementos Theta (n ^ 2) incluso para obtener el primer elemento en la lista.
- ¿Cuál es el factor L en la hipótesis de Riemann?
- Cómo demostrar que si para primo [matemática] p [/ matemática] existe [matemática] m, n \ in \ mathbb {N} [/ matemática] tal que [matemática] p ^ 2 = 2 ^ n 3 ^ m + 1 [/ math], luego [math] p \ leq 17 [/ math]
- La suma de n términos de AP es pn + qn * n. Si pyq son constantes, ¿cómo encuentras la diferencia común?
- Para un entero positivo n, ¿cuántos pares de enteros positivos a, b existen de modo que a, b sean coprimos y ambos sean divisores de n?
- ¿Qué es la función de inversión de Mobius? ¿Cómo se aplica en la teoría de números?
Sé que esto es un poco trampa, y aquí hay otro DS para ser muy lento. Cree una tabla * n y establezca que cada elemento sea 0. Cuando se inserta el elemento i-ésimo, suponga que el elemento insertado es x, el DS selecciona aleatoriamente x * x diferentes ubicaciones de la matriz n * n, y agrega 2 ^ i a cada uno de ellos Cuando desee recuperar el elemento i-ésimo en el DS, debe contar el número total M de ranuras, de modo que el bit i-ésimo sea 1. Entonces este elemento es sqrt (M). Tenga en cuenta que para finalizar esta operación, incluso aplicando cualquier criterio de detención temprana, debe escanear n ^ 2–2n-1 = elementos Theta (n ^ 2) para asegurarse del rango de sqrt (M). Por lo tanto, Theta (n ^ 2) es la mejor complejidad de tiempo de caso de cualquier operación de recuperación.