Available inSpanishEnglishFrenchGermanHindiPortugueseRussian
Big-O y estructuras de datos para entrevistas
Indica el coste en tiempo y memoria de cualquier operación sobre un array, una lista enlazada, un hash map, un árbol, un heap o un trie, incluido el caso amortizado, y defiéndelo en voz alta. Para quien prepara una entrevista técnica o un examen de estructuras de datos, ya conoce los bucles y los hash maps, pero hasta ahora solo reconocía la respuesta de Big-O sin deducirla. Cincuenta y cuatro tarjetas en siete capítulos; los patrones algorítmicos los cubre Patrones para entrevistas de código (Blind 75).
Un programa que cuesta n^2 tarda 1 segundo con 1000 elementos. Estima su tiempo con 2000 elementos.
Unos 4 segundos
— Duplica la entrada y eleva al cuadrado ese factor.
Source
Duplicar n multiplica por cuatro un coste cuadrático, porque (2n)^2 = 4n^2; diez veces la entrada son cien veces el trabajo. La regla de proporciones responde a «¿y si crece la entrada?» sin conocer una sola constante: no hace falta la velocidad de la máquina, solo la forma del crecimiento. Guárdala junto a sus opuestas: en una rutina O(n log n) duplicar n apenas pasa del doble de tiempo, y en O(log n) solo añade un paso.