En función de las limitaciones dadas, ¿cómo decidir qué algoritmo de complejidad de tiempo agotó el tiempo de espera? [cerrado] - algoritmo, tiempo-complejidad

Ej: el algoritmo es O (n), ¿para qué valor aproximado de n (10 ^ x) el tiempo de espera del código en hackerrank? ¿qué pasa con O (nlogn), O (n ^ 2)?

Respuestas

La complejidad del tiempo que se expresa con gran notación O describe el tiempo de ejecución del algoritmo asintóticamente. Esto significa que describe el crecimiento del tiempo de ejecución del algoritmo cuando el tamaño de entrada es infinito.

Una definición formal un poco simplificada:

T(n) = O(f(n)) cuando hay constantes positivas C y n0 eso para cada n > n0 T(n) <= C * f(n)

T(n) es una función de complejidad de tiempo, n Es un tamaño de la entrada.

Por lo tanto, la complejidad del tiempo asintótico no muestra lael tiempo de ejecución del algoritmo, muestra cómo este tiempo de ejecución aumentará con el aumento del tamaño de entrada. Por ejemplo, tener dos algoritmos con tiempo de ejecución. O(n) y O(n*log(n)) no significa que el primer algoritmo sea más rápido en las restricciones específicas del problema (y en el mundo real siempre hay una restricción).

Como resultado, debe tener en cuenta no solo un tiempo de ejecución asintótico sino un factor constante (C constante desde la definición formal) también, el tiempo de ejecución de las operaciones que trata como trivial en el análisis de complejidad de tiempo.

Pero, eso era una teoría. Regresemos al ejemplo. Primero, HackerRank tiene diferentes límites de tiempo para diferentes idiomas / compiladores. Estos límites se pueden encontrar aquí (gracias a Lior kogan). Su código debe finalizar la ejecución antes de que se agote el período de tiempo especificado (eso no es cierto para las soluciones de subprocesos múltiples, pero lo olvidaremos por simplicidad). Hagamos alguna prueba tonta.

const int M = 1000000007;
int sum = 0;
for (int i = 0; i < N; ++i) {
sum = (sum + i) % M;
}
std::cout << sum;

Esto es un trivial O(n) Algoritmo escrito en C ++. Se ajusta al límite de tiempo de un HackerRank con N = 5*10^8 y obtiene error de límite de tiempo con N = 10^9, así que esperaría promedio O(n) algoritmo para estar bien en HackerRank (hoy, siempre pueden actualizar su hardware) con N = 10^7..10^8 dependiendo de la situación.

Si hablamos de cualquier competencia de programación competitiva promedio actual o juez en línea, entonces está bastante seguro con O(n) algoritmo y N = 10^7..10^8, con O(n*log(n)) y N = 10^6..10^7, y con O(n^2) y N = 10^3..10^4. Pero esa es siempre una aproximación muy aproximada y los números reales dependen de muchos factores diferentes.