Available inPortugueseEnglishFrenchGermanHindiRussianSpanish
Big-O e estruturas de dados para entrevistas
Diga o custo em tempo e em espaço de qualquer operação num array, numa lista ligada, num hash map, numa árvore, num heap ou numa trie, incluindo o caso amortizado, e defenda isso em voz alta. Para quem se prepara para uma entrevista de código ou uma prova de estruturas de dados, já conhece loops e hash maps, mas só reconheceu uma resposta em Big-O até hoje. Cinquenta e quatro cartões em sete capítulos; os padrões algorítmicos ficam com Coding Interview Patterns.
Um programa de custo n^2 leva 1 segundo com 1.000 itens. Estime o tempo dele com 2.000 itens.
Cerca de 4 segundos
— Dobre a entrada e depois eleve o fator ao quadrado.
Source
Dobrar n multiplica um custo quadrático por quatro, porque (2n)^2 = 4n^2; dez vezes a entrada dá cem vezes o trabalho. Essa razão responde ao “e se a entrada crescer?” sem precisar de nenhuma constante: você não precisa saber a velocidade da máquina, só o formato do crescimento. Guarde os opostos ao lado: numa rotina O(n log n), dobrar n pouco mais que dobra o tempo; em O(log n), acrescenta um passo. A entrevista quase sempre roda em inglês, e a pergunta chega assim: “and if the input doubles?”.