Pergunta

We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space. However, I feel this does not capture the full story.

Say we have a process that looks like this. Assume memory allocation is O(1) time complexity for simplicity.

process(n):
  mem = allocate(n) 
  for 0 to n:
    ... do O(1) stuff
  end
  free(mem)
  end

The above process takes O(n) time and O(n) space.

Here's another process that takes O(n) time and O(n) space.

process(n):
  for 0 to n:
    ... do O(1) stuff
  end
  mem = allocate(n)
  ... do O(1) stuff
  free(mem)

In the both processes you're using O(n) space. In the first one you're using the space over the course of the entire process. In the second, you're using it only at the very end. Is there a way to formalize the difference?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top