Conocer la complejidad en la programación competitiva

Prerrequisito: Análisis de Complejidad de Tiempo

En general, mientras se realizan problemas de programación competitivos en varios sitios, la tarea más difícil que se enfrenta es escribir el código con la complejidad deseada; de lo contrario, el programa obtendrá un TLE ( límite de tiempo excedido ). Casi nunca se acepta una solución ingenua. Entonces, ¿cómo saber qué complejidad es aceptable?

La respuesta a esta pregunta está directamente relacionada con la cantidad de operaciones que se permiten realizar en un segundo. La mayoría de los sitios en estos días permiten 10 ⁸ operaciones por segundo , solo unos pocos sitios aún permiten 10 ⁷ operaciones. Después de calcular la cantidad de operaciones que se pueden realizar, busque la complejidad correcta observando las restricciones dadas en el problema.

Ejemplo:
Dada una array A[] y un número x, busque un par en A[] con la suma como x.
donde N es:

1) 1 <= N <= 103
2) 1 <= N <= 105
3) 1 <= N <= 108

Para el caso 1
Una solución ingenua que usa dos bucles for funciona, ya que nos da una complejidad de O(N ² ), que incluso en el peor de los casos realizará 10 ⁶ operaciones que están muy por debajo de 10 ⁸ . Por supuesto, O(N) y O(NlogN) también son aceptables en este caso.

Para el Caso 2
, tenemos que pensar en una mejor solución que O(N ² ), ya que en el peor de los casos, realizará 10 ¹⁰ operaciones ya que N es 10 ⁵ . Entonces, la complejidad aceptable para este caso es O(NlogN) que es aproximadamente 10 ⁶ (10 ⁵ * ~10) operaciones muy por debajo de 10 ⁸ u O(N).

Para el caso 3,
incluso O(NlogN) nos da TLE ya que realiza ~10 ⁹ operaciones que superan las 10 ⁸ . Entonces, la única solución aceptable es O (N), que en el peor de los casos realizará 10 ^ 8 operaciones.

El código para el problema dado se puede encontrar en: https://www.geeksforgeeks.org/write-ac-program-that-given-a-set-a-of-n-numbers-and-another-number-x -determina-si-existen-o-no-dos-elementos-en-s-cuya-suma-sea-exactamente-x/