4

Estou usando o livro estruturas de Dados: Algoritmos, Análise da Complexidade e Implementações em JAVA e C/C++ pois ele ajuda com exemplos práticos de implementação.

No capitulo 1 tem o seguinte trecho que me deixou na duvida

O tempo de execução de um algoritmo será representado por uma função de custo T, onde T(n) é a medida do tempo necessário para executar um algoritmo para um problema de tamanho n. Logo, T é chamada 'função complexidade de tempo' do algoritmo. Se T(n) é a medida de memória necessária para a execução do algoritmo, então T é chamada 'função de complexidade espaço. Conforme Ziviani (2004), é importante enfatizar que T(n) não representa diretamente o tempo de execução, mas o número de vezes que certa operação relevante é executada.

Por que que o autor se refere a T de duas maneiras distintas? ficou difícil entender essa variação, tem algum contexto em que uma outra expressão deva ser empregada?

1 Resposta 1

3

Porque tem a ver com duas coisas. A complexidade pode ser medida nesses dois eixos: tempo de execução e espaço ocupado. Esses são os fatores que interessam quando cria ou usa um algoritmo. O quanto ele demora (relativamente) para executar e quanto ele precisa de memória (proporcionalmente).

Talvez o texto esteja amontado e crie confusão, então leia assim:

O tempo de execução de um algoritmo será representado por uma função de custo T, onde T(n) é a medida do tempo necessário para executar um algoritmo para um problema de tamanho n. Logo, T é chamada 'função complexidade de tempo' do algoritmo. É importante enfatizar que T(n) não representa diretamente o tempo de execução, mas o número de vezes que certa operação relevante é executada

Entendeu essa parte?

Agora leia esta nova de forma isolada porque ainda fala de complexidade, mas em outro eixo, então usa-se a mesma notação, mas está falando de outra coisa:

Se T(n) é a medida de memória necessária para a execução do algoritmo, então T é chamada 'função de complexidade espaço

E eu complemento dizendo que ele tem a ver com a quantidade de elementos e não com o espaço efetivo ocupado.

Coloquei no GitHub para referência futura.

Você deve fazer log-in para responder a esta pergunta.

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