0

Complexidade de Algoritmo

Mateus Silva
Mateus Silva

Importância


A complexidade de algoritmos é uma forma de mensurar o tempo de execução de um algoritmo e poder avaliar a sua eficiência. É uma boa prática para avaliar o projeto de um algoritmo.


Formas de avaliar


Existem três formas de avaliar:

  • O melhor caso
  • O melhor caso serve para entender a eficiência do algoritmo em uma situação ideal em que se tem uma noção do que esperar.
  • O caso médio
  • O caso médio avalia baseado em uma situação em que já se espera algo, mas sem ser a situação ideal
  • O pior caso
  • Esse é o mais usado, isso se deve a preocupação que existe caso a pior situação aconteça, pois normalmente mesmo nessa situação o algoritmo ainda precisa ser eficiente. Representado pela notação O.



Essas medidas consideram uma função que mede o tempo, por exemplo:

int n = 10;
for(int i=0; i<n; i++){
  System.out.println("O valor de i = " + i);
}

A função que representaria esse código seria f(n), pois o loop executa n vezes até encerrar, ou seja, essa função representa a quantidade de iterações no loop mesmo que o valor de n mude. Podemos ver que o loop sempre executará n vezes, então o pior caso é O(n).


Agora vejamos o código abaixo que poderia ser usado para imprimir uma matriz de tamanho NxN:

int n = 10;
for(int i=0; i<n; i++){
  for(int j=0; j<n; j++){
   System.out.print("[" + i + "][" + j + "]\t");
  }
  System.out.println("");
} 

Nesse código para cada iteração do for externo o for interno executa n vezes. Como sabemos o for externo vai executar n vezes, portanto os dois juntos executam n.n, portanto a função é quadrática representada por O(n^2).


O impacto


A imagem a seguir demonstra o impacto no tempo de execução de acordo com a complexidade:

Pode-se notar a diferença quando passamos de uma função linear [O(n)] para uma exponencial [O(2^n)] para uma fatorial [O(n!)], portanto a forma como projetamos o algoritmo pode impactar significativamente na sua eficiência.


Exemplo


Um exemplo simples de avaliar a complexidade são com os loops. Suponha uma situação em que existe um vetor e queremos saber se ocorre uma situação de um número x ser seguido de um número y.

//Algoritmo 1
int v[] = {5,7,6,8,10};
n = 5;
x = 8;
y = 10;
for(int i=0; i < n-1; i++){
  if(v[i] == x && v[i+1] == y){
    System.out.println("Achei");
    break;
  }
}

Analisando esse algoritmo podemos ver que ele vai executar o loop n-1 vezes, então no pior caso a sua complexidade é dita O(n-1) que é igual O(n).


Vamos pegar agora outro algoritmo para resolver o mesmo problema

//Algoritmo 2
int v[] = {5,7,6,8,10};
int n = 5;
int x = 8;
int y = 10;
boolean encontrado = false;
 
for(int i=0; i < n-1; i++){
  for(int j=0; j<n; j++){
    if(j<i && v[i] == x && v[j] == y){
      System.out.println("Achei");
      encontrado = true;
      break;
    }
  }
  if(encontrado) break;
}

Já esse algoritmo que realiza a mesma tarefa tem a precisa executar dois for encadeados em que cada um executa até n vezes a complexidade é O(n^2).


Para um vetor de tamanho n=5 não faz muita diferença, mas imagine um vetor que possa ter 500, 1000, 100000, ... elementos.


Qual dos algoritmos você escolheria?


Esse foi apenas um exemplo, existem soluções ainda mais eficientes para esse problema. Além disso a escolha da sua estrutura de dados pode impactar, pois por trás da estrutura vão ser executados algoritmos de busca, ordenação, etc..


Link:


Artigo sobre uso de memória:

https://web.digitalinnovation.one/articles/cuidado-com-o-uso-desnecessario-de-memoria?back=%2Farticles&page=1&order=oldest

Fontes:

  • Introdução a Algoritmos, terceira edição do Thomas H. Cormem.
  • https://medium.com/nagoya-foundation/introdu%C3%A7%C3%A3o-%C3%A0-complexidade-de-algoritmos-4a9c237e4ecc
  • http://wiki.icmc.usp.br/images/d/de/Analise_complexidade.pdf
0
0

Comentários (2)

0
Mateus Silva

Mateus Silva

16/07/2021 16:12

Obrigado, Leandro!

0
Leandro Henrique

Leandro Henrique

16/07/2021 13:05

Ótimo resumo 👏🏻


None

Brasil