0

Tô com uma dúvida em duas questões a respeito do conteúdo de análise algoritmos.


Questões

  1. Em ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema. Análise os itens abaixo.

    I. Para definir o melhor (mais rápido) entre dois algoritmos é necessário implementar ambos e realizar testes.

    II. O tempo de execução de um algoritmo depende, exclusivamente, das operação contidas no mesmo.

    III. Através da contagem de operações processadas por dois algoritmos é possível determinar qual o mais eficiente.

    IV. O tempo de execução de um algoritmo pode depender dos valores de entrada do mesmo.

Na minha análise, eu compreendo que o tempo de execução de um algoritmo, não depende, exclusivamente, das operações contidas nele. Neste caso, eu acredito que o item II esteja incorreto. Talvez, eu esteja errado, mas eu acredito que os outros três itens estejam corretos. No gabarito, apenas dois itens estão corretos e não consigo chegar a resposta.

  1. Dado três algoritmos. A = 50n+10 operações; B = n​²​+15 operações; C = 1000​log​2​n+200 operações. Julgue os itens a seguir.

    I ­ O algoritmo A é mais eficiente para entradas com tamanho maior do que 80.

    II ­ O algoritmo A é o mais indicado para tamanho da entrada menor do que 150.

    III ­ O algoritmo B é o mais indicado para tamanho de entrada maior do que 80.

    IV. ­ O algoritmo B é indicado para tamanho de entrada menor do que 50.

    V. ­ O algoritmo C é melhor para tamanho de entrada entre 50 e 150.

    VI. ­ O algoritmo C possui a menor taxa de crescimento.

Na minha análise sobre à questão dois, o item VI está correto e o item, mas os outros itens acabam confundido, pois, não consigo identificar se um é melhor ou pior que o outro.


Essas são minhas dúvidas, se alguém pode me ajudar pode ser com material também de apoio, estou estudando por questão de conhecimento mesmo, e acho muito importante para um analista em formação compreender sobre o processo de complexidade dos algoritmos.

1
  • Traçar um gráfico no Excel com as três fórmulas vai te ajudar a visualizar as respostas, creio eu.
    – epx
    17/12/2018 às 0:09

2 Respostas 2

6

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​ log​2(​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).

1
  • Que luz, Victor. Obrigado! 17/12/2018 às 13:48
-3

I. Correto. Para comparar o desempenho de dois algoritmos e determinar qual é o mais rápido, é necessário implementar ambos e realizar testes em situações reais ou simuladas. Esses testes podem envolver diferentes tamanhos de entrada e cenários diversos para obter uma avaliação mais precisa.

II. Incorreto. Embora o tempo de execução de um algoritmo seja influenciado pelas operações realizadas, outros fatores também podem impactar o desempenho, como o tamanho dos dados de entrada, a arquitetura do hardware em que o algoritmo é executado, otimizações específicas do compilador, entre outros.

III. Parcialmente correto. A contagem de operações pode fornecer uma ideia geral da complexidade de um algoritmo, mas não é a única métrica para determinar a eficiência. Outros fatores, como a eficiência das operações individuais, o uso de algoritmos assintoticamente mais rápidos (por exemplo, O(log n) vs. O(n^2)), e o impacto dos dados de entrada específicos também precisam ser considerados.

IV. Correto. O tempo de execução de um algoritmo pode variar de acordo com os valores específicos fornecidos como entrada. Alguns algoritmos podem ser mais eficientes para certos tipos de entrada, enquanto podem ser menos eficientes para outras. Portanto, é essencial considerar o desempenho em vários cenários e não apenas em um caso isolado. Isso também está relacionado ao conceito de "complexidade de pior caso", "complexidade de melhor caso" e "complexidade média" de um algoritmo.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .