0

Estava lendo a respeito de buffer circular e sua implementação e me deparei com o termo complexidade de tempo ( no caso, o texto afirma que o buffer circular tem complexidade O (1) ). Pelo que li a respeito, essa é uma métrica que se aplica ao tempo que um algoritmo leva para executar uma tarefa. Seria isso ? Essa métrica se aplica para o código como um todo ou serve também para arrays e outras estruturas de dados? Como medir a complexidade ?

4

1 Resposta 1

2

É isso mesmo, é grosso modo o tempo que o algoritmo leva para resolver o problema.

Quase sempre, quando se discute complexidade de algoritmos, ou citamos vulgarmente que um algoritmo é tratável ou intratável, está a se falar do tempo.

Também existe a complexidade da memória ou armazenamento, ou seja, espaço ocupado pelo algoritmo em RAM ou disco enquanto o trabalho não estiver terminado.

Em certos casos a complexidade de memória ou armazenamento é importante pois pode existir um trade-off (escolha de Sofia) entre complexidade de tempo e complexidade de memória.

Por exemplo, em algoritmos de sort, QuickSort e Merge Sort têm complexidade típica no tempo idêntica. Porém, Merge Sort é O(n) na complexidade de memória, enquanto QuickSort não precisa de memória extra além da própria massa de dados a ser ordenada. Por outro lado, QuickSort pode ter a complexidade de tempo degradada em alguns casos, enquanto Merge Sort mantém a complexidade de tempo sempre baixa. Então é preciso escolher o que for menos prejudicial para o caso de uso.

Como estimar a complexidade, é assunto para um livro. Mas um exemplo simples para introduzir a questão, em pseudocódigo:

def faz_algo(n):
   for i in range(0, n):
      for j in range(0, n):
         ... faz alguma coisa aqui ...

A função acima tem complexidade quadrática no tempo, proporcionalmente a "n", pois tem dois ciclos aninhados, ambos executam "n" vezes. A complexidade de memória é aparentemente O(1) (constante), mas uma conclusão só seria possível sabendo o que "alguma coisa" significa...

3
  • Muito obrigado, ficou bem mais claro agora. É possível dizer que a complexidade de tempo é bem dependente das estruturas de repetição dentro do código ? E a complexidade de memória é o uso de memória que será feito pelo programa ? 5/08/2022 às 22:06
  • Genericamente sim, um programa sem estruturas de repetição teria complexidade no tempo fixa em O(1) mas ainda poderia alocar memória proporcionalmente ao quadrado, cubo, etc. da massa de dados de trabalho
    – epx
    5/08/2022 às 22:57
  • Certo, muito obrigado ! 5/08/2022 às 23:20

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .