Is there a measure of space usage over time?
-
05-11-2019 - |
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