Complexity question on Python 3 lists
d at davea.name
Wed Feb 15 19:45:33 CET 2012
On 02/15/2012 01:20 PM, Franck Ditter wrote:
> What is the cost of calling primes(n) below ? I'm mainly interested in
> knowing if the call to append is O(1), even amortized.
> Do lists in Python 3 behave like ArrayList in Java (if the capacity
> is full, then the array grows by more than 1 element) ?
> def sdiv(n) : # n>= 2
> """returns the smallest (prime) divisor of n"""
> if n % 2 == 0 : return 2
> for d in range(3,int(sqrt(n))+1,2) :
> if n % d == 0 : return d
> return n
> def isPrime(n) :
> """Returns True iff n is prime"""
> return n>= 2 and n == sdiv(n)
> def primes(n) : # n>= 2
> """Returns the list of primes in [2,n]"""
> res = 
> for k in range(2,n+1) :
> if isPrime(k) : res.append(k) # cost O(1) ?
> return res
Yes, lists behave the way you'd expect (see vector in C++), where when
they have to reallocate they do so exponentially.
However, realize that your algorithm is inefficient by a huge factor
more than any time spent expanding lists. The biggest single thing you
need to do is to memoize -- store the list of known primes, and add to
it as you encounter more. Then use that list instead of range(3, xxx,
2) for doing the trial divisions.
More information about the Python-list