CS50 4주차 알고리즘강좌 링크 📚
이번주 강좌는 배열내의 특정값을 찾는 탐색방법과 배열을 정렬하는 것에대한 강좌이다.
컴퓨터는 사람과 다르게 배열의 값들을 한번에 파악할 수 없고 배열속에서 특정값을 찾기 위해서는 전체 배열안의 인덱스값들을 하나씩 검색해야한다. 그렇다면 만약 배열내에서 특정 숫자를 찾는다면 어떠한 방법이 있고 어떤 방식이 유리할까?
알고리즘을 수행하는 데 필요한 시간의 상한선. 컴퓨터과학자들이 코드의 효율성을 표현하기 위해 사용한다. 위의 그림에서 O(n/2)은 O(n)으로 표기되는데 이유는 값이 무한히 커진다면 두개의 선은 같아 보이기 때문이다. 이를 바탕으로 다음과같이 실행시간을 표현할수있다.
Big-O와 마찬가지로 알고리즘을 수행하는데 필요한 시간의 하한선을 표기하는 방법이다.
Omega는 알고리즘을 나타내는 좋은 도구이지만 코드를 구현할 때는 Big-O를 조금 더 신경써야한다.
원하는 원소가 발견될때까지 처음부터 마지막 자료까지 차례대로 검색하는 알고리즘. 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다. 선형검색은 정확하지만 효율적이지 못한 방법이며 검색을 수행하기 이전에 배열을 정렬해 주는것이 효율적이다.
배열을 정렬하는 여러방법중에서 버블정렬, 선택정렬,병합정렬에 관하여 작성하였다.
두개의 인접한 자료값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법.
ex)
위의 예시를 의사코드로 표현한다면,
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
각각의 루프는 n-1번,n-2번 실행되기 때문에 번의 비교가 필요하다. 이를 바탕으로 버블정렬의 Big-O를 표시해본다면 n의 값이 무수히 커졌을때 결국 에 수렴하기 때문에 O()로 표기할 수 있다. 마찬가지로 만약 배열이 모두 정렬되있을 경우를 감안하면 Ω()이다.
배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식.선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
ex)
이를 버블정렬과 마찬가지로 의사코드로 표현한다면,
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item
이며, 여기서 번 만큼 실행되기 때문에, Big-O,Big-Ω 표기법으로 표시한다면 O() , Ω()이다.
앞서 정리한 버블/선택 정렬보다 기능적으로 좋은 정렬 방식이다.
ex)
이를 의사코드로 표현하면
On input of n elements
if n < 2
return
else
sort left half of elements
sort right half of elements
merge sorted halves
이며 해당 코드를 분석해 보면 배열을 반으로나눠서 왼쪽,오른쪽 값들을 정렬하고 두배열을 병합한다. 여기서 병합이란 단순히 두개의 배열을 합치는것이 아닌 내부의 값들을 작은값부터 차례대로 정렬하여 하나의 배열로 만드는것을 의미한다. 병합정렬을 Big-O,Big-Ω 표기법으로 표시한다면 O() , Ω()이다. 물론 시간의 하한선측면에서 보았을때는 선택정렬(Ω())이 우세하지만 최악의 경우에는 병합정렬의 속도가 더 빠르기때문에 어느정도의 희생은 불가피하다.