[CS 기초지식 알고리즘] -20일차

1. 탐색

 

- 선형 탐색

인덱스의 처음부터 끝까지 탐색

 

- 이진 탐색

배열이 sorted, 중간 인덱스부터 시작해서 작거나 큰 쪽으로 이동하며 탐색

 

 

2. 알고리즘 표기법

 

O, Ω 로 표기

 

O :실행 시간의 상한(최악의 수까지 고려했을 때의 알고리즘 속도)

 

Ω: 실행 시간의 하한(최대로 운이 좋았을 때의 알고리즘 속도)

 

3. 선형 검색

typedef 이름 으로 새로운 자료구조를 형성해서 사용할 수 있다!

 

선형 탐색은 시간복잡도가 높은 알고리즘

 

 

4. 버블 정렬

두 개의 인접한 자료 값을 비교하면서 위치를 교환해나가는 방식

 

-> 너무 많은 시간이 걸릴 수 있음

 

자료가 sorted 되어있다면 O,

else면 정렬하는 시간도 포함되어 마찬가지로 시간이 오래 걸린다

 

 

5. 선택 정렬

 

가장 작은 수를 찾아 첫 번째 위치와 교환해주는 방식

 

 

6. 실행시간

 

실행시간의 상한

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

 

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n)
• Ω(n)
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

 

7. 재귀

재귀의 개념

dra함수가 4 -> 3-> 2-> 1순으로 계속 자기 자신을 호출

for문이 h==1일때부터 쭉 그리는 로직

 

8. 병합 정렬

 

원소가 하나가 될때까지 반으로 계속 쪼개면서 좌 정렬, 우 정렬, 병합 하는 과정을 거치는 알고리즘

 

속도는 빠르지만, 차지하는 메모리가 크다는 단점이 존재