need help defining Constant memory requirement
Andrew Koenig
ark at acm.org
Sun Sep 19 01:26:57 EDT 2004
"Jani Yusef" <jani at persian.com> wrote in message
news:d3be1825.0409182100.612a5dcb at posting.google.com...
>I have a HW problem stated as shown at the top of the solution. The
> thing is is that I am not 100% sure wtf constant memory means. Well, I
> think I do but I am confused. Does my solution use contant memory in
> terms of the length of the list i? If so why not and how could I
> change it to be so? I am sure the solution is O(n) since the list must
> only iterated once and the dictionary is O(1), correct?
> Thanks for the help!!
Constant memory means the same as O(1) memory -- in other words, that it is
possible to place an upper bound on the total amount of memory used (aside
from the input) regardless of how large the input is.
> #You are given a sequence S of n numbers whose values range from 1 to
> n-1.
> #One of these numbers repeats itself once in the sequence.
> #(Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}).
> #Write a function that finds this repeating number using a constant
> #amount of memory and linear time.
> import sys
> i=[1,3,4,5,3]
> tally={}
> for a in i:
> if tally.has_key(a):
> print "repeated number is "+str(a)
> sys.exit(0)
> else:
> tally[a]=1
> print "no repeat found"
This program doesn't use constant memory, because tally might conceivably
have as many as n-1 elements, where n is the number of elements in the
input. Therefore the total amount of space needed is O(n), not O(1).
One question you might ask: Is the entire input sequence available at once?
Is it permissible to modify its elements?
More information about the Python-list
mailing list