부스트코스 - CS50

알고리즘

입력을 출력값으로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열

검색이나 정렬같은 문제를 푸는 알고리즘?
배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능

- 선형검색 (linear search)

인덱스를 처음부터 하나씩 끝까지 증가 시키면서 값을 찾음 >> 값이 끝쪽에 있으면 손해, 정렬되지 않은 배열에서 유용

- 이진검색 (binary search)

배열이 정렬되어 있을때 배열 중간의 값을 확인하고 찾으려는 값보다 크면 왼쪽 중간의 값을 확인 반복, 작으면 오른쪽 중간의 값 확인 반복

- 버블정렬 (bubble sort)

이웃한 값과 크기를 비교하여 위치를 교환한다. 교환이 일어나지 않을시 루프를 종료하면 실행시간을 Ω(n)까지 줄일수있다
배열 안에 존재하는 값의 개수 세기

- 선택정렬 (selection sort)

배열의 처음부터 끝까지 최소값을 탐색하여서 최소값을 가장 왼쪽에 위치한 값과 위치를 바꾼다

- 병합정렬 (merge sort)

배열을 반복해서 원소가 한 개가 될때까지 절반씩 나누고 절반씩 나눈 값을 순서에 맞게 병합하며 정렬

---

시간 복잡도

Big O 알고리즘 실행시간의 상한, 최악조건

• O(n^2) - 버블정렬, 선택정렬
• O(n log n) - 병합정렬
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

Big Ω 알고리즘 실행시간의 하한, 최상조건

• Ω(n^2) - 선택정렬

• Ω(n log n) - 병합정렬

• Ω(n) - 버블정렬

• Ω(log n)

• Ω(1) - 선형 검색, 이진 검색

Θ 알고리즘 실행시간의 하한과 상한이 같음

• Θ(n^2) - 선택정렬
• Θ(n log n) - 병합정렬
• Θ(n)
• Θ(log n)
• Θ(1)

재귀함수
함수가 본인 스스로를 호출함 반복..