Conteúdo principal
Ciência da Computação
Curso: Ciência da Computação > Unidade 1
Lição 3: Notação assintóticaNotação assintótica
Até agora, analisamos a busca linear e a busca binária contando o número máximo de tentativas necessárias. Mas o que realmente queremos saber é quanto tempo esses algoritmos demoram. Estamos interessados no tempo, não só nas suposições. Os tempos de execução da busca linear e da busca binária incluem o tempo necessário para gerar e checar palpites, mas algoritmos não se resumem a isso.
O tempo de execução de um algoritmo depende do quão demorado é para um computador executar as linhas de código do algoritmo e isto depende da velocidade deste computador, da linguagem de programação, e do compilador que traduziu o programa da linguagem de programação para o código que executa diretamente no computador, entre outros fatores.
Vamos pensar com mais cuidado no tempo de execução de um algoritmo. Podemos usar a combinação de duas ideias. Primeiro, precisamos determinar quanto tempo o algoritmo leva em termos do tamanho da entrada. Esta ideia parece intuitiva, não é mesmo? Já vimos que o máximo de tentativas necessárias em busca linear e em busca binária aumenta conforme aumenta o tamanho do array de candidatos. Ou pense sobre um GPS. Se ele conhecesse apenas o sistema de rodovias principais, e não todas as pequenas estradas secundárias, ele deveria ser capaz de buscar rotas mais rapidamente, certo? So we think about the running time of the algorithm as a function of the size of its input.
A segunda ideia é que precisamos focar em quão rápido uma função cresce com o tamanho da entrada. Chamamos isso de taxa de crescimento do tempo de execução. Para manter as coisas tratáveis, precisamos simplificar a função até evidenciar a parte mais importante e deixar de lado as menos importantes. Por exemplo, suponha que um algoritmo, sendo executado com uma entrada de tamanho n, leve 6, n, squared, plus, 100, n, plus, 300 instruções de máquina. O termo 6, n, squared torna-se maior do que os outros termos, 100, n, plus, 300, uma vez que n torna-se grande o suficiente, 20 neste caso. Abaixo temos um gráfico que mostra os valores de 6, n, squared e 100, n, plus, 300 para valores de n variando entre 0 e 100:
Podemos dizer que este algoritmo cresce a uma taxa n, squared, deixando de fora o coeficiente 6 e os termos restantes 100, n, plus, 300. Não é realmente importante que coeficientes usamos, já que o tempo de execução é a, n, squared, plus, b, n, plus, c, para alguns números a, is greater than, 0, b, e c, sempre haverá um valor de n para o qual a, n, squared é maior que b, n, plus, c, e essa diferença aumenta juntamente com n. Por exemplo, aqui está um gráfico mostrando os valores de 0, comma, 6, n, squared e 1000, n, plus, 3000 de modo que reduzimos o coeficiente de n, squared por um fator de 10 e aumentamos as outras duas constantes por um fator de 10:
O valor de n para o qual 0, comma, 6, n, squared se torna maior que 1000, n, plus, 3000 aumentou, mas sempre haverá um ponto de cruzamento, independentemente das constantes.
Descartando os termos menos significativos e os coeficientes constantes, podemos nos concentrar na parte importante do tempo de execução de um algoritmo — sua taxa de crescimento — sem sermos atrapalhados por detalhes que complicam sua compreensão. Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica. Vamos estudar suas três formas: notação \Theta, notação O, notação \Omega.
Este conteúdo é uma colaboração entre os professores Thomas Cormen e Devin Balkcom da Dartmouth Computer Science e a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
- o que o "n" e o "a" representam ??(12 votos)
- O "a" representa a concavidade da parábola nas equações de 2º grau ou quadráticas. Já o "x" é a raiz ou raízes reais ou complexas da equação (do 2º grau).(16 votos)
- Boa tarde,
Eu iniciei os estudos em "Ciência da Computação" por algoritmos, mas ao chegar nessa parte de notação assintótica eu me perdi completamente.
Estou estudando matemática pelo próprio khanacademy, mas ainda não cheguei em nenhuma parte parecida com Notação Big-θ ou big-Θ.
Tem alguma parte anterior por onde deveria ter começado? Desde já agradeço.(11 votos)- Neste contexto de análise de algoritmos, a constante 'a' representa o número de instruções a serem realizadas. A variável 'n' representa o número de dados de entrada a serem processados.(6 votos)
- O que é notação assintótica?(4 votos)
- De forma simplificada, entenda como a "análise do comportamento de algoritmos perante uma entrada grande de dados".(10 votos)
- Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica.(5 votos)
- só um comentário: engraçado aqui os comentários serem de 2 anos para trás.(3 votos)
- sim hahahaha me sinto no yahoo(2 votos)
- no final disponibilizam certificado?(2 votos)
- Não, até onde eu sei os cursos não têm certificado. É pelo conhecimento, mesmo.(2 votos)
- Alguém poderia me explicar os gráficos?(1 voto)
- No primeiro gráfico temos as retas de duas funções. A reta vermelha é exponencial (6n²) e a reta azul é linear (100n + 300). Sabemos que n representa o tamanho da entrada. Esse gráfico mostra o crescimento das funções de acordo com o tamanho da entrada.(2 votos)
- olá porém se em uma função se for considerado apenas a aplicação em um intervalo inferior ao ponto de cruzamento, a parte mais significativa será a parte anteriormente desprezada.(1 voto)