Questão de Tecnologia da Informação · FCC TRT19 2022 (nº 23)

A ordem de complexidade (ou notação Big O) descreve como o tempo de execução ou o uso de memória de um algoritmo cresce à medida que o tamanho da entrada (N) aumenta, focando no termo dominante que mais impacta o desempenho para grandes valores de N.

• (A) Incorreta: Dizer que é "sempre ineficiente, mesmo para valores pequenos de N" é um exagero. Para N pequeno, N-1 comparações (melhor caso) ou mesmo (N*(N-1))/2 (pior caso) podem ser perfeitamente aceitáveis e rápidas. A ineficiência de um algoritmo O(N²) se torna mais evidente para valores grandes de N.
• (B) Correta: A ordem de complexidade é determinada pelo termo de maior grau nas expressões. No caso médio (NCmédio ≅ (N*(N-1))/4 - 1/2) e no pior caso (NCpior ≅ (N*(N-1)-1)/2), o termo dominante é N². Por exemplo, (N*(N-1))/4 = (N² - N)/4. Quando N é muito grande, N² é muito maior que N, então o termo N² é o que define o crescimento do número de comparações. Portanto, o método é de ordem de complexidade quadrática, ou O(N²).
• (C) Incorreta: O(N²) (quadrático) não é considerado "muito eficiente" para algoritmos de ordenação, especialmente quando comparado a algoritmos O(N log N) (linearítmicos). Além disso, um vetor em ordem decrescente é frequentemente o pior caso para muitos algoritmos de ordenação O(N²), não o caso médio.
• (D) Incorreta: A complexidade no melhor caso é O(N-1), que é equivalente a O(N) (linear), não O(N log N) (linearítmica). O termo "linearítmica" é a armadilha aqui, pois O(N-1) é simplesmente O(N). O melhor caso geralmente ocorre quando o vetor já está ordenado, não apenas parcialmente.
• (E) Incorreta: O problema fornece apenas o número de comparações, não o número de trocas. Não podemos inferir o número de trocas a partir das informações dadas. Além disso, N-1 comparações (melhor caso) não é "um número muito grande" e a conclusão de "muito ineficiente" em todos os casos é uma generalização incorreta.