A introdução da notação O permite que a análise de complexidade computacional classifique os algoritmos em classes que determinam seu desempenho. Os algoritmos mais eficientes são aqueles que executam em um tempo proporcional a uma constante e, a partir daí, temos o aumento do tempo de execução segundo as ordens definidas. Assim, qual das alternativas a seguir é verdadeira:
O(n²) tem maior complexidade que O(n log n).
O(1) tem maior complexidade que O(n).
O(n) tem maior complexidade que O(n²).
O(1) tem maior complexidade que O(log n).
O(log n) tem maior complexidade que O(n log n).
Ed
ano passado
A notação O é usada para descrever a complexidade de algoritmos, e a relação entre as diferentes classes de complexidade é importante para entender o desempenho dos algoritmos. Vamos analisar as alternativas: 1. O(n²) tem maior complexidade que O(n log n) - Verdadeiro. O(n²) cresce mais rapidamente que O(n log n) conforme n aumenta. 2. O(1) tem maior complexidade que O(n) - Falso. O(1) é constante e sempre menor que O(n). 3. O(n) tem maior complexidade que O(n²) - Falso. O(n) cresce mais lentamente que O(n²). 4. O(1) tem maior complexidade que O(log n) - Falso. O(1) é constante e menor que O(log n). 5. O(log n) tem maior complexidade que O(n log n) - Falso. O(log n) cresce mais lentamente que O(n log n). Portanto, a alternativa verdadeira é: O(n²) tem maior complexidade que O(n log n).