Algorithm 썸네일형 리스트형 Sieve of Eratosthenes, 에라토스테네스의 체 에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를 찾기 위한 간단한 알고리즘이다.1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.3. 해당 숫자의 배수들을 집합에서 모두 지운다. 4. 2로 돌아간다. 끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.- 모든 합성수composite number 는 최.. 더보기 Asymptotic analysis, 점근적 표기법. 알고리즘의 성능을 분석하기위해 점근적 표기법을 이용해 시간복잡도 사용한다. 단순히 특정 입력 값에 따른 실행시간(running time)을 비교하는게 아니라, 입력값이 증가함에 따른 Running time의 rate of growth를 표현한 것이 시간 복잡도(time complexity)이다. Big-theta Running time에 대한 점근적인 한계값을 Big theta라 한다. 즉, 알고리즘의 평균 시간복잡도를 말한다. Big-O 빅오는 running time에 대한 점근적인 상한값을 말한다. 즉, 알고리즘의 최악의 시간 복잡도이다. 보편적으로 ‘시간 복잡도’는 최악의 케이스를 커버하능 빅오를 말한다. Big-omega 빅 오메가는 running time에 대한 점근적인 하한값을 말한다.. 더보기 이전 1 다음
