원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식 7 4 5 2 6 3 8 1 먼저 숫자들을 반으로 나눈다. 7 4 5 2 | 6 3 8 1 그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다. 7 4 | 5 2 | 6 3 8 1 마지막으로 한 번 더 나눈다. 7 | 4 | 5 2 | 6 3 8 1 이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합한다. 단, 이 때 작은 숫자가 먼저 오도록 한다. 4와 7의 순서를 바꿔서 병합하는 것 4 7 | 5 2 | 6 3 8 1 마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있다. 4 7 | 2 5 | 6 3 8 1 그럼 이제 4 7과 2 5 두 개의 ..
알고리즘
선형검색, 이진검색, 버블정렬, 선택정렬의 실행시간은 어떻게 될까? 실행시간의 상한 O(n^2): 선택 정렬, 버블 정렬 O(n log n) O(n): 선형 검색 O(log n): 이진 검색 O(1) 실행시간의 하한 Ω(n^2): 선택 정렬, 버블 정렬 Ω(n log n) Ω(n) Ω(log n) Ω(1): 선형 검색, 이진 검색 만약 정렬이 모두 되어 있는 숫자 리스트가 주어질 때, 바깥쪽 루프를 “교환이 일어나지 않을때” 까지만 수행하면 버블 정렬의 하한은 **Ω(n)**이 된다. 상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것 실행시간의 하한 Ω(n^2): 선택 정렬 Ω(n log n) Ω(n): 버블 정렬 Ω(log n) Ω(1): 선형 검색, 이진 검색 최종 정리본 선형 검색: O(N) ..
배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다. 실행 시간의 상한 : O(n^2) 실행 시간의 하한 : Ω(n^2) 실행 시간의 상한, 하한 모두 버블 정렬과 동일하다.
두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 것. 버블 정렬은 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다. 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 도 있다. 아래와 같이 정렬이 진행된다. 3 6 5 2 7 4 1 8 3 6 5 2 7 4 1 8 (교환) 3 5 6 2 7 4 1 8 (교환) 3 5 2 6 7 4 1 8 3 5 2 6 7 4 1 8 (교환) 3 5 2 6 4 7 1 8 (교환) 3 5 2 6 4 1 7 8 중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1, n-2번 반복되므로 (n-1)*(n-2)번의 비교 및 교환이 필요하다. 실행 시간의 상한 : O(n^2) 실행 시간의 하한 : 정렬이 되어 ..
원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 것 효율성 그리고 비효율성 선형 검색 알고리즘은 정확하지만 효율적이지 못한 방법이다. 리스트의 길이가 n일 경우, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행된다. 반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우이다. → 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용 실행 시간의 상한 : n개의 리스트일 경우 n번만큼 실행해야 하기 때문에 O(n) 실행 시간의 하한 : 운이 좋아 첫 시도 때 찾고자 하는 값이 있을 수 있다 Ω(1)
Big O Big Ω 알고리즘의 실행 시간의 상한과 하한을 표기할 수 있다. Big O 표기법(빅오) - 실행 시간의 상한 O는 “on th order of”의 약자로 “~만큼의 정도로 커지는” 이라고 볼 수 있다. O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다. 아래 목록과 같이 Big O표기가 실행 시간을 나타내기 위해 많이 사용된다. O(n^2) O(n log n) O(n) - 선형 검색 O(log n) - 이진 검색 O(1) Big Ω 표기법(오메가) - 실행 시간의 하한 예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다. 이진검색도 운이 좋다..
선형검색 처음부터 끝까지 하나씩 값을 확인하는 방법 이진검색 만약 값들이 정렬되어있다면 중간 숫자부터 시작해서 찾고자 하는 값과 비교해 그보다 작은 , 또는 큰 값으로 이동을 반복해 값을 확인학는 방법 생각해보기 만약 정렬되어 있지 않은 배열이 있다면, 선형검색이 빠를까 이진검색이 빠를까? 💡 배열이 정렬되더 있지 않다면 이진 검색을 사용할 수 없고, 선형검색이 최선이다.
