Conteúdo principal
Ciência da Computação
Curso: Ciência da Computação > Unidade 1
Lição 3: Notação assintóticaFunções em notação assintótica
Quando usamos a notação assintótica para expressar a taxa de crescimento do tempo de execução de um algoritmo, em termos do tamanho de entrada n, é bom ter algumas coisas em mente.
Vamos começar com algo fácil. Suponha que um algoritmo demorou uma quantidade constante de tempo para ser executado, independentemente do tamanho da entrada. Por exemplo, se você recebeu um array que já estava em ordem crescente e você tinha que localizar o menor elemento, a execução levaria um tempo constante, já que o elemento mínimo deve estar no índice 0. Como gostamos de usar funções de n em notação assintótica, você poderia dizer que esse algoritmo é executado num tempo \Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis. Por quê? Porque n, start superscript, 0, end superscript, equals, 1, e o tempo de execução do algoritmo está contido em um fator constante de 1. Na prática, não escrevemos \Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis, em vez disso, escrevemos \Theta, left parenthesis, 1, right parenthesis.
Agora suponha que um algoritmo levou um tempo de \Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis para ser executado. Você também pode dizer que ele levou um tempo de \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Sempre que a base do logaritmo for constante, não importa em que base usamos a notação assintótica. Por que não? Porque existe uma fórmula matemática que diz:
para todos os números positivos a, b e n. Portanto, se a e b são constantes, então log, start base, a, end base, n e log, start base, b, end base n diferem apenas por um fator de log, start base, b, end base, a, e isso é um fator constante que podemos ignorar em notação assintótica.
Portanto, podemos dizer que o pior cenário do tempo de execução de uma busca binária é \Theta, left parenthesis, log, start base, a, end base, n, right parenthesis para qualquer constante positiva a. Por quê? O número de chutes é, no máximo, log, start base, 2, end base, n, plus, 1, gerar e testar cada chute leva um tempo constante, e configurar e retornar o valor também leva um tempo constante. No entanto, por uma questão de prática, frequentemente escrevemos que a busca binária leva \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis porque cientistas da computação gostam de pensar em potências de 2.
Há uma ordem para as funções que vemos frequentemente quando analisamos algoritmos usando notação assintótica. Se a e b são constantes e a, is less than, b, então o tempo de execução \Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis cresce mais lentamente do que um tempo de execução \Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis. Por exemplo, o tempo de execução \Theta, left parenthesis, n, right parenthesis, que é \Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis, cresce mais lentamente do que um tempo de execução \Theta, left parenthesis, n, squared, right parenthesis. Os expoentes também não têm de ser inteiros. Por exemplo, o tempo de execução de \Theta, left parenthesis, n, squared, right parenthesis cresce mais lentamente do que um tempo de execução \Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis, que é \Theta, left parenthesis, n, start superscript, 2, comma, 5, end superscript, right parenthesis.
O gráfico a seguir compara o crescimento de n, n, squared e n, start superscript, 2, point, 5, end superscript:
Logaritmos crescem mais lentamente do que os polinômios. Ou seja, \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis cresce de forma mais lenta que \Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis para qualquer constante positiva a. Mas uma vez que o valor de log, start base, 2, end base, n cresce quando n cresce, \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis possui um crescimento mais rápido que \Theta, left parenthesis, 1, right parenthesis.
O gráfico a seguir compara o crescimento de 1, n e log, start base, 2, end base, n:
Aqui está uma lista de funções em noção assintótica que encontramos muitas vezes quando analisamos algoritmos, listadas do crescimento mais lento para o crescimento mais rápido.
- \Theta, left parenthesis, 1, right parenthesis
- \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis
- \Theta, left parenthesis, n, right parenthesis
- \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis
- \Theta, left parenthesis, n, squared, right parenthesis
- \Theta, left parenthesis, n, squared, log, start base, 2, end base, n, right parenthesis
- \Theta, left parenthesis, n, cubed, right parenthesis
- \Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis
- \Theta, left parenthesis, n, !, right parenthesis
Observe que uma função exponencial a, start superscript, n, end superscript, em que a, is greater than, 1, cresce mais rápido do que qualquer função polinomial n, start superscript, b, end superscript, em que b é qualquer constante.
A lista acima não é exaustiva, existem muitas funções com tempos de execução que não estão listadas aqui. Você vai encontrar com algumas delas em sua jornada na ciência da computação.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
- Pelo amor de jeová, traduzam esse conteúdo.(15 votos)
- Acho que vou lendo até ver se entendo. Eu sonharia com um video ou algo que mostrasse um exemplo.(9 votos)
- Comparar as funções com coeficiente 1 no GeoGebra torna tudo muito claro!(4 votos)