[Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도

인트로 합병 정렬 또는 병합 정렬은 $O(NlogN)$ 시간 복잡도를 갖는 정렬 알고리즘으로 분할 정복 패러다임에 기반한다. 추가로 삽입 정렬, 버블 정렬, 선택 정렬이 추가적인 자료구조 없이 정렬하는 Inplace 정렬이라면 병합 정렬은 정렬한 데이터를 추가적인 임시 공간에 저장한다. 병합 정렬(Merge Sort) : 개념 앞서 언급했듯 병합 정렬은 분할 정복 패러다임에 기반한 알고리즘으로 큰 문제를 아주 작은 문제로 나눈 뒤 작은 문제를 해결하며 최종적으로 큰 문제를 해결한다. 다음과 같은 데이터가 배열에 저장되어 있다. 분할 : 본 배열을 더 이상 쪼갤 수 없을 때까지 쪼개면 [3] [44] [38] [5] [47] [15] [36] [26] 다음과 같은 형태가 된다. 정복 : 두 집합을 하나로 ..

• format_list_bulleted Algorithm/정렬
• · 2021. 10. 10.
• textsms

[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도

인트로 이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다. 이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다. 이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다. 본 포스팅 말미에 코드와 시간 복잡도 계산법을 상세히 적어놨으니 참고하시길 바랍니다. 이진 탐색 : 개념 이진 탐색은 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다. 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 16.
• textsms