020. 10억 개 전화번호에서 이름 찾기 : 이진 검색
이진 검색
-
후보 범위가 한 항목으로 좁혀질 때까지 찾고자 하는 항목을 포함하고 있는 리스트를 반으로 나누는 과정은 반복하는 검색
-
분할 정복이라는 일반적인 전략의 한 가지 예
-
단계의 수는 전체 항목의 크기를 2로 계속 나눠 항목 크기가 1에 도달하게 되는 횟수
-
정렬이 되어있다고 가정
-
수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가
이진 검색의 예
-
숫자 맞추기(숫자 범위 : 1~16, 맞출 숫자 : 1)
-
숫자 범위인 16/2=8의 값을 부른다. DOWN! [1~8], [9~16]
-
8의 절반인 4 을 부른다. DOWN! [1~4], [5~8]
-
4의 절반인 2을 부른다. DOWN! [1~2], [3~4]
-
정답은 1
-
log : 4
-
021. 검색을 쉽게 만드는 정렬 : 선택 정렬 vs 퀵 정렬
정렬
- 항목을 순서대로 배열해서 검색이 빨리 실행될 수 있도록 해줌.
선택 정렬
제자리 정렬 알고리즘 중 하나로 리스트 중 최소값을 찾아 맨 앞에 위치한 값과 교체하고 리스트의 길이만큼 반복하는 것.
퀵 정렬
- 다른 원소와의 비교로 정렬을 수행하는 비교 정렬 중 하나.
- 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
정렬의 시간복잡도
실행시간 증가 그래프
시간복잡도 & 공간복잡도
- 시간복잡도와 공간복잡도는 알고리즘의 성능을 평가하는 방법 입니다.
시간복잡도 vs 공간복잡도
공간복잡도보다 시간복잡도를 더 우선해서 생각합니다.
시간복잡도
-
시간복잡도는 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도입니다.
-
시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 분석한 결과입니다.
-
시간 복잡도는 알고리즘의 절대적인 실행 시간이 아닌 알고리즘 수행에 필요한 연산 횟수를 나타냅니다. (연산의 종류는 산술, 대입, 비교, 이동을 말합니다)
빅오(big-O) 표기법
- 시간복잡도를 계산하는 대표적인 방법입니다.
빅오 표기법은 최악의 경우를 가정합니다.
전체 길이가 N인 배열에서 A의 값이 어디 있는지 찾아야 합니다. 하나의 값을 확인하는 데 걸리는 시간이 1초라고 가정했을 때 A가 가장 앞에 있다면 해당 문제는 1초만에 해결됩니다. 하지만 그렇다고 선형 탐색을 O(1)로 표현하지 않습니다. 이처럼 시간복잡도는 최선,평균,최악중 최악의 경우로 시간복잡도를 평가합니다.
