Analise de Complexidade

Lista de Questões
Análise de Complexidade

1) Defina complexidade computacional e assintótica. Como uma difere da outra?
A complexidade computacional indica quanto esforço é necessário para se aplicar um algoritmo, ou quão custoso ele é. Esta complexidade está ligada às dificuldades e transtornos que ocorrerão durante o decorrer de um projeto (como tempo de processamento, espaço utilizado no disco, entre outros) e a complexidade assintótica está ligado a funções complexas contidas dentro de um programa, como uma função que fornece um valor n tendendo ao infinito e faz essa função crescer cada vez mais.

2) Para que serve a notação O-grande? Defina-a.
É uma notação utilizada para especificar a complexidade assintótica, ou seja, estimar a taxa de crescimento da função para então limitar superiormente esta função em um valor constante (por exemplo, evitar que uma função aumente muito).

3) Quais são as propriedades da notação O-grande? O que elas representam?
A notação O define a cota assintótica superior. Ela serve para limitar superiormente uma função dentro de um fator constante. Exemplo: uma função quadrática g(n)=3n2 cresce mais rapidamente que uma linear f(n)=7n+13. Logo, dizemos que f(n) é O(g(n)).
Um algoritmo é O(1) se o número de operações fundamentais é limitado por uma constante. f(n)=O(g(n)) significa que algum múltiplo constante de g(n) é um limite assintótico superior sobre f(n).

4) Quais são os possíveis problemas usando-se essa notação?
Os resultados expressos em notação O devem ser interpretados com cuidado, pois indicam apenas que o tempo de execução do programa é proporcional a um determinado valor ou que nunca supera determinado valor; na verdade o tempo de execução pode ser inferior ao valor indicado e pode ser que o pior caso nunca ocorra.

5) Dê exemplos de complexidades.
Complexidade constante
- Quando o tempo de execução do algoritmo independe do tamanho da entrada;
- Os passos do algoritmo são executados um número fixo