Notação Big O Explicada com Exemplos de Código
Uma busca em um dicionário Python leva cerca de 100 nanossegundos, não importa se o dicionário tem 1.000 ou 1.000.000 de chaves. Um laço duplo que procura duplicatas em uma lista leva meio milissegundo com 200 itens e 136 milissegundos com 3.200. Dezesseis vezes a entrada, quase 280 vezes a espera. Mesma máquina, mesmo Python. A notação Big O é o nome dessa diferença. O que a notação Big O mede Big O descreve como o tempo de execução (ou o uso de memória) de um trecho de código cresce conforme a entrada aumenta. Não é uma leitura de cronômetro, e não importa se o seu notebook é rápido ou lento. O que importa é a forma da curva de crescimento: ao dobrar a entrada, o tempo dobra, quadruplica ou quase não muda? ...