Imagina que eres el probador de preguntas. Su trabajo sádico es garantizar que el número máximo de personas obtenga el “Límite de tiempo excedido” si no aplican el algoritmo requerido -> O (√N) por consulta. ¿Cómo distribuiría sus consultas? Vamos a aplicar algo de teoría del juego.
Bueno, podríamos hacer que casi todos ellos actualicen consultas. Pero una actualización será una operación O (1) en una matriz simple. Eso significa una complejidad de alrededor de O (1) por consulta. No hay salario este mes.
Del mismo modo, muchas consultas tampoco son buenas. Esto se debe a que una persona podría preprocesar y almacenar el RESULTADO de IZQUIERDA = 1 a DERECHA = 1,2,3,… .N en el tiempo O (N) y responder cada consulta como RESULTADO [DERECHA] – RESULTADO [IZQUIERDA]. O (1) operaciones por consulta nuevamente.
- ¿Qué esquema o algoritmo de compresión se usa en el formato de video 4K?
- ¿Son 2 horas de entrenamiento de rompecabezas de algoritmos por día durante un año suficiente para prepararse para la entrevista de Google?
- ¿Por qué no hay implementación de montón de Fibonacci en la API Java estándar?
- ¿Qué es un algoritmo para generar todas las combinaciones posibles de un conjunto dado de letras (por ejemplo, 'a', 'b', 'c', 'd', 'e')?
- ¿Por qué la complejidad temporal de los algoritmos de Edmond Karps O (VE ^ 2)? A mí me parece O (E * (E + V)).
Las mejores pruebas resultan cuando tiene exactamente la mitad del número de actualizaciones y el resto como consultas. Esto asegura que ambas operaciones necesiten la misma cantidad de tiempo para ejecutarse.
Debemos asegurarnos de que nuestro algoritmo pueda sobrevivir a las operaciones de actualización Q y consulta Q. En la descomposición en bloque, se necesita tiempo B para una actualización. Y las consultas tardan N / B en completarse.
[matemáticas] Tiempo total = B + N / B [/ matemáticas]
Vamos a diferenciar por B para obtener los mínimos.
[matemática] d (Tiempo total) / dB = 1 – N / B ^ 2 = 0 B = √N [/ matemática]
Podemos diferenciar la cantidad nuevamente para verificar que se trata de un mínimo
[matemática] d ^ 2 (Tiempo total) / dB ^ 2 = [/ matemática] [matemática] 2N / B ^ 3> 0 [/ matemática]
La cantidad es mayor que cero y, por lo tanto, un mínimo. Por lo tanto, decimos que el mejor tamaño de bloque posible es √N.
La técnica de la que habla tomaría solo la raíz cúbica de N por actualización, pero tomaría N / cube_root (N) = N ^ (2/3) por consulta. “Límite de tiempo excedido”.
He hecho un video sobre descomposición de raíz cuadrada. Habla sobre el algoritmo y su implementación.
¡Aclamaciones!
