Gabarito disponível
Um militar implementou uma função em linguagem JAVA para resolver um problema hipotético do Centro de Dados da Marinha.
public class Main {
public static int somaTriangular(int[][] matriz) {
int n = matriz.length;
int soma = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
soma += matriz[ i ][ j ];
}
}
return soma;
}
public static void main(String[] args) {
int[][] examploMatriz = {{1,0,0}, {4,5,0}, {7,8,9}};
int result = somaTriangular(examploMatriz);
System.out.println(result);
}
}
Assinale a opção que apresenta corretamente a complexidade em notação O da função somaTriangular, de acordo com Szwarcfiter (2010).
public class Main {
public static int somaTriangular(int[][] matriz) {
int n = matriz.length;
int soma = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
soma += matriz[ i ][ j ];
}
}
return soma;
}
public static void main(String[] args) {
int[][] examploMatriz = {{1,0,0}, {4,5,0}, {7,8,9}};
int result = somaTriangular(examploMatriz);
System.out.println(result);
}
}
Assinale a opção que apresenta corretamente a complexidade em notação O da função somaTriangular, de acordo com Szwarcfiter (2010).
Resolução comentada
Os laços aninhados executam n(n+1)/2 iterações, o que dá O(n²).
O laço externo roda n vezes e o interno roda i+1 vezes, somando 1+2+...+n = n(n+1)/2 operações. Esse total é quadrático em n, logo a complexidade é O(n²).
Análise das alternativas
A) e B) Errada: são complexidades menores, sem laços aninhados proporcionais a n. C) Errada: O(n) seria um único laço. E) Errada: O(n³) exigiria três laços aninhados.
Referência: Szwarcfiter (2010), Estruturas de Dados e Algoritmos, análise de complexidade.
Resolução comentada do VaiConcursos.