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!!!!!!
A alternativa correta é: D - F, V, F
Vamos analisar cada uma das afirmações dadas na questão para entender melhor o tema da complexidade computacional e justificar as alternativas.
( ) 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.
Essa afirmação é falsa. A função de complexidade de tempo de um algoritmo na verdade descreve a ordem de crescimento do tempo de execução em função do tamanho da entrada, não o tempo exato de execução do programa.
( ) 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).
Essa afirmação é verdadeira. A análise de pior caso nos dá uma garantia de que o tempo de execução do algoritmo não excederá f(n), independentemente da entrada específica.
( ) Na análise do caso médio toma-se a média aritmética do pior caso com o melhor caso.
Essa afirmação é falsa. A análise de caso médio considera a média dos tempos de execução para todas as entradas possíveis, ponderada pela probabilidade de cada entrada, e não simplesmente a média aritmética do pior e do melhor caso.
Agora vamos revisar as alternativas incorretas:
- A - V, V, V: Errou ao considerar a primeira e a terceira afirmação como verdadeiras.
- B - F, F, F: Errou ao considerar a segunda afirmação como falsa.
- C - V, F, F: Errou ao considerar a primeira afirmação como verdadeira.
- E - F, F, V: Errou ao considerar a terceira afirmação como verdadeira.
Como você pode ver, entender a definição correta dos conceitos de complexidade de tempo e suas análises (pior caso, melhor caso, e caso médio) é essencial para responder corretamente questões desse tipo em concursos públicos.
Se precisar de mais alguma explicação ou tiver dúvidas adicionais, estou à disposição!