Calculando o comportamento dos algoritmos
A análise da complexidade de um algoritmo demonstra qual seria o seu desempenho com entradas de tamanho tendendo ao infinito. No entanto, para um número razoável de elementos, isso pode não ser o caso.
Para o seu caso, existe algum número n para o qual, além dele, o algoritmo linear será sempre mais rápido. Entretanto, determinar qual é esse n é um tanto difícil, pois ele pode variar de máquina para máquina e uma operação no algoritmo f1 pode demorar um tempo diferente do que uma operação no algoritmo f2.
Assim sendo, até um determinado ponto, o algoritmo f2 deve ser mais rápido, sendo então alcançado e ultrapassado por f1 deste ponto em diante.
Supondo que os dois algoritmos tenham operações com as mesmas velocidades e rodem na mesma máquina sob as mesmas condições (o que provavelmente não é uma suposição válida no mundo real, mas vamos presumir isso para facilitar o cálculo), podemos encontrar o valor de n onde um algoritmo ultrapassa o outro assim:
f1(n) = f2(n)
2n² + 5n = 500n + 4000
2n² - 495n - 4000 = 0
n = (495 ± sqrt(495² - 4 * 2 * - 4000)) / (2 * 2) [aplicação da fórmula de Bhaskara]
n = (495 ± sqrt(245025 + 32000)) / 4
n = (495 ± sqrt(245025 + 32000)) / 4
n = (495 ± sqrt(277025)) / 4
n = (495 ± 526.33) / 4
n = (495 + 526.33) / 4 OU n = (495 - 526.33) / 4
n = 1021.33 / 4 OU n = -31.33 / 4
n = 255.33 OU n = -7.83
Como n < 0 não faz sentido (o tamanho da entrada não tem como ser menor que zero), então:
n = 255.33
Ou seja, para um n ≤ 255, o algoritmo f1 é mais rápido. Para n ≥ 256, o algoritmo f2 será mais rápido. Prova disso é que:
f1(255) < f2(255) → 131325 < 131500
f1(256) > f2(256) → 132352 > 132000
Por que usa-se apenas o termo de maior grau e despreza-se as constantes?
Novamente, friso que a análise de complexidade é dada com um n tendendo ao infinito. Neste caso, numa expressão do tipo 2n² + 5n, o fator 5n rapidamente se tornará desprezível perto do 2n², e portanto pode ser deixado de lado. Semelhantemente, numa expressão 500n + 4000, o fator 500n crescerá tanto de modo que o 4000 se tornará desprezível. Por isso é que apenas o termo de maior grau é considerado na análise de complexidade.
Quanto às constantes multiplicativas, ao comparar-se expressões com diferentes graus quando n tende ao infinito, a constante também acaba por ser irrelevante. Por exemplo, sejam p e g duas constantes, onde p é muito pequena e g é muito grande. Ao comparar-se pn² com gn tendo n tendendo ao infinito, haverá algum ponto onde o fator pn² crescerá de tal modo que ultrapassará o valor de gn (tal como fiz no cálculo acima), e portanto a expressão de maior grau sempre vai ultrapassar a de menor grau, independente das constantes utilizadas. Desta forma, quando n tende ao infinito, faz sentido apenas de falar-se do termo de maior grau, desprezando-se os coeficientes e os termos de menor grau.
Uma outra consequência da eliminação das constantes é que se você tem dois algoritmos A e B com complexidades de tempo de graus diferentes, não importa qual seja a máquina mais rápida, mesmo que uma delas execute instruções 10 vezes mais rapidamente que a outra (ou 100 vezes, ou um milhão de vezes), sempre haverá algum ponto n onde o algoritmo com a complexidade de maior grau será mais lento que o de menor grau (é verdade que é possível que este ponto seja para um tamanho de entrada monstruoso e para um tempo absurdo e fora do aceitável no mundo real, mas mesmo assim esse ponto existe).
Por outro lado, se os dois algoritmos C e D têm complexidades com o mesmo grau, mas o C é mais 2 vezes mais lento, basta eu conseguir uma máquina que seja mais do que 2 vezes mais rápida e então o algoritmo C ultrapassará o D. Os termos de menor grau não irão interferir nisso para um n suficientemente grande porque ao conseguir uma máquina mais rápida, eu estarei multiplicando/dividindo os tempos dos termos de maior grau também, de forma que para um valor suficiente de n a diferença de desempenho obtida com os termos de maior grau irá superar qualquer deficiência referente aos termos de menor grau.
Exemplos concretos
Um exemplo concreto onde algo assim acontece é na multiplicação de números: o algoritmo aprendido na escola é O(n2), enquanto que o algoritmo de Karatsuba é bem mais complexo (e portanto tem constantes multiplicativas maiores), mas é O(n(log2 3)). Para números grandes, o algoritmo de Karatsuba é mais rápido. Para números pequenos, usa-se o algoritmo aprendido na escola.
Aliás, há também o algoritmo de Schönhage–Strassen que bate o algoritmo de Karatsuba em números bem grandes, com dezenas de milhares de casas decimais, tendo ele uma complexidade O(n log(n) log(log(n))).
Assim sendo, para números pequenos, o algoritmo mais rápido é o da escola. Para os números de tamanho médio, o Karatsuba mostra-se mais rápido. Para os números bem grandes, usa-se o Schönhage–Strassen.
Finalmente, o algoritmo de Fürer em teoria bate o Schönhage–Strassen tendo complexidade O(n log(n) 23 log*(n)), mas suas constantes multiplicativas são tão altas que ele teoricamente só supera o Schönhage–Strassen em números com dezenas de quintilhões de dígitos (e por esse motivo ele é mais uma curiosidade teórica do que algo que você usaria na prática).
Ah, e eu nem entrei no mérito do algoritmo de Toom-Cook que é uma generalização do algoritmo da escola e do Karatsuba.
Um outro caso é o algoritmo Timsort que é um algoritmo que utiliza internamente, de forma seletiva e dinâmica, o merge sort ou o insertion sort em diferentes partes dos dados dependendo de como eles estão organizados, tentando aproveitar o melhor de cada algoritmo onde for conveniente e tentando se aproveitar de ordenações parciais já existentes.
Ou seja, se você quiser perguntar "qual o algoritmo mais eficiente?", deve-se perguntar primeiro "quais são os tamanhos da entrada que me interessam?" - esse detalhe pode mudar tudo.
O uso de O, Ω e Θ
Além disso, a análise com o O se refere ao pior caso, não ao caso médio ou ao melhor caso. Por exemplo, o quicksort para entradas aleatórias tem um caso médio bem melhor que merge sort. Apesar de ambos terem casos médios O(n log n), o quicksort tem constantes multiplicativas menores. Entretanto, o pior caso do quicksort é O(n2), enquanto que o do merge sort sempre é O(n log n).
A notação O significa um limite superior. Ou seja, um algoritmo com complexidade O(n²) nunca vai levar um tempo pior do que quadrático para executar. Entretanto, esse limite pode ser frouxo, tal como é no quicksort, onde embora ele execute no máximo em tempo quadrático, ele pode em vários casos executar em um tempo bem menor do que isso.
Também há o limite inferior, que é dado por Ω. O algoritmo quicksort é Ω(n log n) porque ele nunca roda em tempo menor do que n log n. Ou seja, enquanto que o O diz qual é o pior caso, o Ω diz qual é o melhor. O uso de Ω não é muito comum, mas serve para se definir um ponto a partir do qual seria impossível uma melhoria que não se restrinja apenas às constantes multiplicativas ou aos termos de menor grau. Por exemplo, é sabido que Ω(n log n) é o limite inferior para algoritmos de ordenação de elementos baseados em comparação, e portanto sabe-se que não existe e que é algo impossível ter-se um algoritmo de ordenação de elementos com tempo melhor do que n log n.
E quando o melhor e o pior caso coincidem, surge o Θ. Um algoritmo pode ser dito Θ(k) se ele sempre executar em tempo k, tanto no melhor quanto no pior caso. Por exemplo, o merge sort é Θ(n log n), pois em todos os casos ele tem um tempo proporcional a n log n.