CS50x 2023 - Lecture 3 - Algorithms
Linear/Binary search
- Linear search: 리스트나 배열에서 원하는 값을 찾기 위해 처음부터 끝까지 순차적으로 탐색하는 방법
- Binary search: 오름차순으로 정렬된 리스트에서 특정 값을 찾는 알고리즘으로, 중간 값과 비교하여 검색 범위를 반으로 줄여가면서 값을 찾아나가는 방법
Running time
아래 표기법들이 알고리즘의 성능을 분석하고 비교하는 데에 사용되는데, 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지에 대한 예측하는것임. Big O가 일반적으로 가장 널리 사용되는 표기법이다.
- Big O 표기법 (O 표기법): 알고리즘의 시간 복잡도의 상한선을 나타냄(알고리즘이 실행될 때 필요한 최대시간/worst case)
- Omega 표기법 (Ω 표기법): 알고리즘의 시간 복잡도의 하한선을 나타냄.(알고리즘이 실행될 때 필요한 최소시간/best case)
- Theta 표기법 (Θ 표기법): 알고리즘의 시간 복잡도의 상한선과 하한선이 같을 때 사용됩니다. (Big O = Omega)
phonebook.c 예시
strcmp함수는 두 string을 input으로 받아서 이들을 비교한뒤 같으면 0을 return하고, 그렇지 않으면 다른 정수를 return한다.
forloop 안팎에서 return 0, return 1을 하고 있는데, 저것들을 쓰지 않으면 Found, Not found 둘다 출력함. return 0을 가운데 넣음으로써 break point를 주는 효과가 있다. 근데 또 return 0 대신 break로 바꾸면 여전히 forloop이 끝까지 돌아서 Not found까지 출력됨. 여튼 return 0을 하는것이 이 코드가 여기서 끝난다는 명시를 가장 쉽게 하는 방법이라고 한다.
struct
5~10번줄처럼 person이라는 struct를 만들어서, 16~20번줄처럼 array의 각 위치에 값을 넣어준뒤 밑에서 똑같이 linear search를 하는 예시임. csv file, database등 대량 데이터를 불러올때 저렇게 미리 정의한 구조로 받으면 효율적이란 얘기.
Selection sort/Bubble sort
- Selection Sort(선택 정렬): 선택 정렬은 리스트에서 가장 작은값을 찾아서 맨 앞부터 순서대로 정렬하는 방법임. 최소값을 찾아서 리스트의 첫 번째 위치와 교환하고, 그 다음으로 작은 값을 찾아서 두 번째 위치와 교환하는 방식으로 정렬을 진행한다.
- Bubble Sort(버블 정렬): 버블 정렬은 인접한 두 원소를 비교하여 필요한 경우 서로 교환하면서 정렬하는 방법임. 큰 값을 리스트의 뒤쪽으로 '거품처럼' 올려서 정렬하는 것으로, 순차적으로 비교하면서 큰 값이 맨 뒤로 이동하게 된다.
Comparing Algorithms
selection sort의 연산이 일어나는 횟수를 계산해보면 위와 같다. 알고리즘의 성능을 따져보면 n이 무한히 커진다고 가정했을 때, Big O표기법(longest time/worst performance)로 n제곱으로 나타낸다.(n은 무시됨. 어차피 n제곱이 훨씬 커서) Omega 표기법(shortest time/best performance)으로도 n제곱인데, 이미 sort가 되어있다고 해도 array나 list의 가장 끝값으로 갈때까지 작은수는 하나만 기억하기 때문이다. 이렇게 Big O, Omega 표기법 둘다 n제곱으로 같아서 selection sort는 theta 표기법을 사용할수 있다.
bubble sort의 연산이 일어나는 횟수를 계산해보면 위와 같으며, Big O표기법은 selection sort와 같은 n제곱이지만 Omega표기법은 이미 sort가 된 경우 마지막으로 한번더 첨부터 끝까지 확인하는 작업까지 포함하여 그냥 n이다. 따라서 theta를 사용할수 없다.
Recursion(재귀)
12번줄부터 정의되고 있는 draw()함수를 보면, 19번째 줄처럼 자기 자신을 계속 부르고 있다.
4를 입력하면 draw(4)에선 draw(3)을 부르고, draw(3) 안에선 draw(2)를 부르고.. 결국 draw(0)가 되어 16번째 줄로 인해 return이 된다.
이것이 역으로 출력되어 #
##
###
#### 와 같은 피라미드 모양이 출력된다.
Merge sort
리스트를 반으로 나눈 뒤 각각을 정렬하고, 정렬된 부분 리스트들을 병합하여 전체 리스트를 정렬하는 방법을 재귀적으로 사용하여 최종 결과를 얻는 방법이다. 스페이스는 좀 더 잡아먹지만(반씩 정렬된 array를 담아둘 array가 필요하므로, array가 여러개 필요함) 시간은 훨씬 적게 걸린다. big O표기법, Omega표기법 모두 n log n이어서 theta 또한 n log n이다.