【알고리즘】 2-1강. 탐색 알고리즘 실험

2-1강. 탐색 알고리즘 실험

 

추천글 : 【알고리즘】 2강. 탐색 알고리즘  

---

1. 개요 [본문]

2. 탐색 알고리즘 실험 [본문]

3. 실험을 수행한 컴퓨터의 사양 [본문]

---

 

1. 개요 : 파이썬 프로그램 실행을 위하여 3.8 버전으로 jupyter notebook을 사용 [목차]

 

 

2. 탐색 알고리즘 실험 : 이 문제를 푸는 데 있어서 데이터의 범위는 0 ~ input_size - 1을 고려 [목차]

⑴ 탐색 알고리즘의 구현

① 선형 탐색 알고리즘

○ 탐색 여부를 반환하는 선형 탐색 알고리즘

 

 

○ 탐색된 원소의 순서를 반환하는 선형 탐색 알고리즘

 

 

○ 정렬된 배열에 대한 선형 탐색 알고리즘

 

 

② 이진 탐색 알고리즘 

○ 재귀함수를 이용한 알고리즘

 

 

○ 반복을 이용한 알고리즘

 

 

④ 랜덤 숫자 생성

 

 

⑵ 결과 1. 입력이 이미 sorting이 된 경우 : [0, 1, ··· ]에 대한 배열을 고려

 

 

⑶ 결과 2. 입력이 sorting이 되지 않았을 경우 : [0, 1, ··· ]에 대한 배열을 고려

 

 

⑷ big O time complexity와 실제 실행시간의 관계

① 입력이 이미 sorting이 된 경우

○ log f(N) / log N의 기울기를 보니 예상대로 linear search는 N의 big O time complexity를 가짐

○ binary search는 log N인데 0처럼 나타난 것은 N ≫ 1에 대해 N이 log N에 비해 상당히 커지기 때문

○ binary search의 경우 operation time이 매우 짧기 때문에 CPU 스케줄링 이슈로 인해 input size에 대해 operation time이 불규칙한 것으로 보임 

② 입력이 sorting이 되지 않았을 경우

○ log f(N) / log N의 기울기를 보니 예상대로 linear search는 N의 big O time complexity를 가짐

○ 예상과는 달리 sorting이 되지 않은 경우 sorting이 된 경우보다 linear search의 operation time이 더 짧다는 것을 알 수 있었는데, 이것도 또한 CPU 스케줄링 이슈로 인한 것이라고 보여짐 

 

 

3. 실험을 수행한 컴퓨터의 사양 [목차]

⑴ CPU의 종류 및 성능 : Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz

⑵ 운영체제의 이름 및 version : Microsoft Windows 10 Pro

⑶ 장착된 DRAM의 종류 및 크기 : 32.0GB DDR3

 

입력: 2021.09.29 00:25