Disciplina: Noções de Informática 0 Curtidas
A notação _______, representa uma complexidade _________, ou seja
A notação _______, representa uma complexidade _________, ou seja, o tempo de execução aumentará de forma linear com o tamanho da entrada. Outras complexidades que são comumente encontradas são: O(log N), O(N2), O(N3). Vale ressaltar que em termos de eficiência teremos que: O(1) < O(log N) < _____ < O(N2) < O(N3) < O(2N), ou seja, um algoritmo com complexidade O(N) é mais eficiente que _______.
Escolha a opção que completa corretamente as lacunas.
a) F(N) / linear / O(10) / O(N2).
b) O(N) / linear / O(N) / O(N2).
c) O(N) / quadrática / O(log N2) / O(log N).
d) F(N) / quadrática / O(N) / O(log N).
e) O(N) / linear / O(N) / O(log N).
Solução
Alternativa correta: b) O(N) / linear / O(N) / O(N2). De acordo com o gabarito AVA.
A notação O(N) representa uma complexidade linear, indicando que o tempo de execução aumentará de forma proporcional ao tamanho da entrada. Isso significa que, conforme o tamanho da entrada (N) aumenta, o tempo de execução do algoritmo também aumenta na mesma proporção. As complexidades O(log N), O(N2) e O(N3) representam respectivamente complexidades logarítmica, quadrática e cúbica. Em termos de eficiência, a ordem é O(1) < O(log N) < O(N) < O(N2) < O(N3) < O(2N), o que significa que um algoritmo com complexidade O(N) é mais eficiente que O(N2).
Assuntos: Notação Assintótica na Análise de Algoritmos, Complexidade Linear em Algoritmos, Eficiência Computacional e Tamanho da Entrada
Vídeo Sugerido: YouTube