Fast Fibonacci Transform

빠른 피보나치 항 구하기 피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다. def fib(n): if n < 3: return (0, 1)[n] return fib(n-1) + fib(n-2) 하지만 이 함수는 지극히 비효율적이라 %time fib(35) Wall time: 7.05 s Out[7]: 9227465 이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다. #

체를 사용하여 소수 집합 구하기

가장 빠른 알고리듬 현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @Robert William Hanks가 개발한 아래 알고리듬이다. def primes(n): “””Return a list of primes under n””” sieve = [True] * (n/2) for i in xrange(3, int(n**0.5)+1, 2): if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) return [2] + [2*i+1 for i in xrange(1, n/2) if sieve[i]]

Shell 정렬

Shell 정렬 Shell 정렬은 “분할 증분 정렬”(diminishing Incremental Sort)이라고도 불리는 방법으로 삽입정렬을 원래 리스트를 더 작은 서브리스트들로 나눠서 정렬함으로써 성능을 향상시키는 방법이다. 즉 리스트를 더 작은 조각들로 나눈다음 각각을 삽입정렬을 사용하여 정렬한다. 이 때 서브리스트들을 나누는 기준을 정하는 방법이 독특한데, 연속된 원소들로 구성된 서브리스트를 나누는게 아니라 i개씩 건너뛰고 원소들을 선택하여 서브리스트를 만든다. 이 때 i는 gap이라고도 불리운다.

병합정렬

Merge Sort Shell 정렬은 보통의 삽입정렬을 리스트를 쪼개는 방식으로 성능을 향상시킨 예이다. 이러한 분할정복방식을 검색에 도입한 알고리듬이 여럿 있는데, 병합정렬(merge sort)도 그 중 하나이다. 병합정렬은 리스트를 재귀적으로 절반으로 나누어 처리하는 방식이다. 만약 리스트가 비어있거나 원소가 하나만 있다면 그 자체로 정렬되어 있다고 보고, 그것이 베이스 케이스1가 된다.