Complexidade de Algoritmos

Em programação competitiva é de extrema importância saber a complexidade do algoritmo desenvolvido. Normalmente, é fácil desenvolver um algoritmo que resolva um problema lentamente, mas o verdadeiro desafio é projetar um algoritmo rápido/eficiente.

A complexidade de tempo de um algoritmo estima quantas operações o algoritmo usará para alguma entrada. A ideia é representar a eficiência como uma função cujo parâmetro é o tamanho da entrada. Calculando a complexidade de tempo, pode-se descobrir se o algoritmo é rápido o suficiente sem implementá-lo.

Leia o Capítulo 2 do livro "Competitive Programmer’s Handbook".