문과도 이해 쌉가능! 알고리즘 10분 기초개념 탑재. - YouTube
내용 정리
선형 검색
2 | 6 | 1 | 9 | 3 | 4 | 10 | 7 | 0 | 8 |
위 같은 배열이 있다고 때 인덱스 0 번부터 맨 마지막 인덱스까지 원하는 값을 한 인덱스씩 열어보며 찾는 법
Worstcase 시간복잡도 : O(n)
단, 값을 추가할때 python append 처럼 값을 뒤에 붙이기만 해도 됨
이진검색
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
위 같이 정렬된 배열에서, 9를 찾는다고 하면 예를 들어 5가 있는 칸부터 검색을 시작,
9가 5보다 작으므로, 오른쪽 칸들, 6-10이 들어있는 칸으로 이동,
6,7,8,9,10에서 정중앙은 8, 8보다 9가 크므로 오른쪽칸으로 이동
9,10 중 9와 9를 비교, 같으므로 검색 성공.
Worstcase 시간복잡도 : O(log n)
단, 값을 추가할때도 정렬된 배열이어야 하기 때문에 배열을 늘리고, 값을 옮기는 등의 추가 작업이 필요함
그리고 처음부터 값들을 정렬된 상태로 만들어야함