Temporada 1 · Como pensar em código · 14
Algoritmos e complexidade (intuição de Big-O)
Objetivo: Fazer uma busca que lia 1.000.000 de nomes um a um responder em milissegundos, sem mudar a lista.
O apresentador é uma representação do autor feita com inteligência artificial.
Entre para responder e somar XP.
Entrar ou criar contaEste lab faz parte da temporada completa.
- 1. Qual a complexidade do código inicial, que lê a lista inteira no pior caso? Responda no formato O(...).
- 2. Qual a complexidade da busca que você escreveu? Responda no formato O(...).
- 3. Para achar um nome entre 1.000.000, quantas vezes, no máximo, você corta a lista pela metade? Arredonde para o inteiro mais próximo.
Ao revisar código da IA, procure um loop dentro de outro sobre os mesmos dados, ou uma busca que lê a lista inteira dentro de um laço. Rode com 10 vezes mais dados antes de aprovar: se o tempo sobe 100 vezes, o custo cresce com o quadrado. Escreva a versão simples, meça e otimize só onde os dados crescem.