A Complexidade Computacional é a área da Ciência da Computa...
Questão estranha.. não consegui encontrar resposta para as alternativas I e II.
I - A função de complexidade de tempo de algoritmo indica o tempo necessário para executar o programa que implementa o algoritmo em função do tamanho da entrada.
Definição do Wikipedia: "Em ciência da computação, a complexidade de tempo de um algoritmo quantifica a porção de tempo tomada por um algoritmo para rodar em função do tamanho da entrada do problema". Não encontrei diferença que justifique a alternativa ser Falsa.
II Se f é uma função de complexidade baseada na análise de pior caso, o custo de aplicar o algoritmo nunca é maior do que f(n).
Para este exemplo, o Quicksort em seu pior caso é de complexidade O(n²), portanto maior que O(n).
Se alguém puder explicá-la, agradeceria.
Oi Leonardo, o caso II creio que ele esteja falando que a função f(n) é o pior caso. Por ser o pior caso, nada virá acima dela com relação à complexidade do algoritmo. Foi assim que entendi pelo menos! A meu ver ele não está dizendo que f(n) é O(n).
Verdade Yane Wanderley, consegui compreender!
Obrigado pela explicação!
Leonardo, com relação à II, quando ele diz f(n) ele não está se referindo à complexidade linear O(n). f(n) é a função de complexidade de tempo do algoritmo. De fato ela nunca será maior que o pior caso do algoritmo. Portanto, II está correta.
Creio que o erro da I está em afirmar que a função de complexidade indica o tempo necessário para executar o programa, o que não é necessariamente verdade. Por exemplo, podemos ter uma função de tempo em que o programa é executado em 5n³ + 2n² + 500n unidades de tempo, porém sua função de complexidade será apenas O(n³).
Força Guerreiro!!!!!!