I. Para definir o melhor (mais rápido) entre dois algoritmos é necessário implementar ambos e realizar testes.
Considerando que isso é uma pergunta sobre análise de algoritmos, se você tiver eles apenas rascunhados num papel em pseudocódigo, você consegue determinar a complexidade deles. Se um deles for O(n), enquanto o outro é O(n²), você não precisa implementá-los e rodá-los em uma máquina real para saber qual é o mais rápido. Logo, isso é falso.
II. O tempo de execução de um algoritmo depende, exclusivamente, das operaç[ões] contidas no mesmo.
IV. O tempo de execução de um algoritmo pode depender dos valores de entrada do mesmo.
A afirmação IV já mostra o porquê da II ser falsa. Obviamente que os valores de entrada influenciam diretamente o tempo de execução de um algoritmo. Aliás, normalmente o tempo de execução é dado como uma função dos valores ou do tamanho da entrada. Logo, a II é falsa e a IV é verdadeira.
III. Através da contagem de operações processadas por dois algoritmos é possível determinar qual o mais eficiente.
Se um der O(n) e o outro O(n²), fica claro qual é o mais eficiente. Logo, isso é, em geral, verdadeiro. Uma análise mais refinada tal como 50n + 10 ou 48n + 30 operações também serve para responder isso. Logo isso daí é verdadeiro. E é exatamente sobre isso que a segunda questão diz.
Em que intervalos o algoritmo A é mais eficiente que o B?
Para saber isso, vamos ver o ponto onde ambos se encontram. Ou seja, onde 50n + 10 = n² + 15:
50n + 10 = n² + 15
0 = n² − 50n + 15 − 10
n² − 50n + 5 = 0
n = (50 ± sqrt(50² − 4 × 1 × 5)) / (2 × 1)
n = (50 ± sqrt(2500 − 20)) / 2
n = (50 ± sqrt(2480)) / 2
n = (50 ± 49.8) / 2
n' = (50 − 49.8) / 2
n' = 0.2 / 2
n' = 0.1
n" = (50 + 49.8) / 2
n" = 99.8 / 2
n" = 49.9
O que isso significa? Como a equação calculada foi y = n² − 50n + 5, temos que isso é o tempo do B menos o tempo do A. Logo, se for negativo, o B é mais rápido. Se for positivo, o A é mais rápido. Se isso der zero, os dois têm o mesmo desempenho. Os pontos onde os dois têm o mesmo desempenho (as raízes da equação) ocorrem com entradas de tamanho 0.1 e 49.9.
A concavidade da parábola resultante é voltada para cima, logo, na maioria dos casos (os que estão além das raízes), o B demora mais. Nos demais casos (entre as raízes), o A demora mais. Logo, o B é mais rápido para entradas de tamanho 1 a 49. Enquanto que o A é mais rápido para as entradas de tamanho 0 ou maior ou igual a 50. Prova disso é que:
A: 50 × 0 + 10 = 10 (mais rápido)
B: 0² + 15 = 15
A: 50 × 1 + 10 = 60
B: 1² + 15 = 16 (mais rápido)
A: 50 × 49 + 10 = 2460
B: 49² + 15 = 2416 (mais rápido)
A: 50 × 50 + 10 = 2510 (mais rápido)
B: 50² + 15 = 2515
Agora, façamos o mesmo para o A em comparação ao C:
50 n + 10 = 1000 log2(n) + 200
Infelizmente, achar a raiz dessa equação é algo complicado. O mesmo acontece ao comparar B com C. O problema da questão 2 necessita que os tempos de A, B e C sejam todos comparados, e embora você possa utilizar equações para achar uma resposta, tal como ao comparar A com B, em muitos casos, encontrá-las pode ser algo difícil e/ou trabalhoso.
No entanto, podemos utilizar um programinha e montar uma tabela de valores para nos ajudar:
function log2(x) {
return x == 0 ? 0 : Math.log(x) / Math.log(2);
}
for (var n = 0; n <= 600; n++) {
var a = 50 * n + 10;
var b = n * n + 15;
var c = 1000 * log2(n) + 200;
// Para exibir o c com duas casas decimais se não for inteiro.
var cx = Math.round(c * 100) + "";
cx = c % 1 === 0
? c
: cx.substring(0, cx.length - 2) + "," + cx.substring(cx.length - 2);
var melhor = ""
if (a <= b && a <= c) melhor += "A";
if (b <= a && b <= c) melhor += "B";
if (c <= a && c <= b) melhor += "C";
var tr = $("<tr></tr>");
$("<td>" + n + "</td>").appendTo(tr);
$("<td>" + a + "</td>").appendTo(tr);
$("<td>" + b + "</td>").appendTo(tr);
$("<td>" + cx + "</td>").appendTo(tr);
$("<td>" + melhor + "</td>").appendTo(tr);
$("#t").append(tr);
}
td, th {
border-color: black;
border-width: 1px;
border-style: solid;
}
table {
border-spacing: 0;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<table id="t">
<tr>
<th>N</th>
<th>A</th>
<th>B</th>
<th>C</th>
<th>Melhor</th>
</tr>
</table>
Nesse programa, há uns poréns quanto à função logaritmo. Essa função produz zero quando a entrada é 1 e produz valores negativos para entradas no intervalo [0, 1), indo a −∞ quando a entrada é 0. Para resolver isso, vamos considerar que a saída seja zero quando a entrada é zero, vez que tempo de execução negativo não existe.
Assim, olhando para a tabela, temos que:
- Para N = 0, o A é o melhor.
- Para 1 ≤ N ≤ 49, o B é o melhor.
- Para 50 ≤ N ≤ 147, o A é o melhor.
- Para N ≥ 148, o C é o melhor.
Logo:
I. O algoritmo A é [o] mais eficiente para entradas com tamanho maior do que 80.
Falso. Isso só é válido para os casos onde a entrada está entre 50 e 147. A partir daí, o C é o mais eficiente.
II. O algoritmo A é o mais indicado para tamanho da entrada menor do que 150.
Falso. Para entradas de tamanho até 49, o B é o melhor. Para uma entrada de tamanho 148 ou 149, o C é melhor.
III. O algoritmo B é o mais indicado para tamanho de entrada maior do que 80.
Falso. Só é o melhor quando a entrada tem tamanho menor que 50.
IV. O algoritmo B é indicado para tamanho de entrada menor do que 50.
Verdadeiro desde que você desconsidere o caso N = 0 (que em vários tipos de algoritmos, é algo que não existe).
V. O algoritmo C é [o] melhor para tamanho de entrada entre 50 e 150.
Falso. O A é o melhor quando a entrada está entre 50 e 147.
VI. O algoritmo C possui a menor taxa de crescimento.
Verdadeiro. É por esse motivo que a partir de um certo ponto (N ≥ 148), ele sempre é melhor do que os outros algoritmos. Por taxa de crescimento, você pode entender como derivada:
- A: d(50x + 10) = 50.
- B: d(x² + 15) = 2x.
- C: d(1000 log2(x) + 200) = 1000 × 1 / (x × ln(2)) = 1442.7 x−1.
Observe o grau de cada uma das expressões. O grau da derivada de A é 0. O grau da derivada de B é 1. O grau da derivada de C é −1. Quanto menor o grau da derivada, menor é a taxa de variação.
No entanto, você nem precisa olhar para a derivada para ver que a taxa de crescimento de C é menor. Basta saber que uma função quadrática (B) cresce mais rápido que uma função linear (A), que por sua vez cresce mais rápido que uma função logarítmica (C). E portanto:
- Quadrático = O(n²).
- Linear = O(n).
- Logarítmico = O(log n).
E com isso, você nem precisa olhar o resto para ver qual cresce a uma taxa maior ou menor. Só teria que fazer isso se fosse para comparar duas funções da mesma classe (duas quadráticas diferentes, por exemplo).