ksw_devlog

이분탐색 N 개의 수가 크기 순서대로 배열되어 있을 때, 특정한 수 K가 몇 번째 위치에 있는지 빠르게 찾는 방법 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 한 번에 배열이 절반씩 줄어들기 때문에, 시간 복잡도는 O(log2 N)이다.(밑 2) N이 100만일 때, log2 N은 약 20이므로 20개 정도의 수만 보면 충분하다

알고리즘 성능 평가 알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다. 그 중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다. 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 1. 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같은 소스라면 시간이 적게 걸리는 것이 좋은 소스이다. ** 시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 ..