문제해결실무 중간고사 대체과제

소개글

"문제해결실무 중간고사 대체과제"에 대한 내용입니다.

목차

1. Brute-force와 k-d tree의 최단 이웃 탐색 시간 비교

2. Approximate nearest neighbor search (근사 최단 이웃 탐색)
1) 정확도를 희생하여 빠르게 탐색할 수 있는 아이디어 제시
2) 구현 및 실험

참고문헌

본문내용

brute-force방식과 kd_tree방식의 결과로는 DIM이 16까지는 brute-force가 kd_Tree보다 시간이 많이 걸렸고, kd_Tree의 경과시간 또한 1초를 넘지 않았습니다. 하지만, DIM이 32가 되자 kd_tree의 시간 값이 기하급수적으로 늘어나 brute-force의 시간 값보다 많이 나왔으며, DIM이 32이상일 때부터는 brute-force의 시간이 kd_Tree의 시간보다 적게 나온다는 것을 확인하였습니다.

각 알고리즘의 시간복잡도가 궁금하여 찾아보았더니 brute-force는 O(n)이었고, kd_Tree는 탐색할 시 평균 O(log n), 최악의 경우 O(n)이라고 나와 있었고 log 1000000 일 경우 6이라는 값이 나와 차원이 늘어나도 시간에는 영향을 안준다고 생각했습니다. 여러 번 시행해본 결과 21차원까지는 kd_Tree가 더 적은 시간을 소모하였으나 22차원부터 결과가 뒤집히기 시작했고, brute-force 방식은 완전탐색이라 모든 결과 값을 다 시행하기 때문에 kd_tree가 항상 brute-force보다 값이 적게 나와야되는데 위의 결과를 얻어 당황했습니다.

참고 자료

mathworks 사이트 https://kr.mathworks.com/help/stats/classification-using-nearest-neighbors.html
위키백과 사이트 https://ko.wikipedia.org/wiki/%EC%B5%9C%EA%B7%BC%EC%A0%91_%EC%9D%B4%EC%9B%83_%ED%83%90%EC%83%89