[모두를 위한 컴퓨터 과학] Ch4. 알고리즘(Algorithm)

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)

 

💃  해당 강의를 듣고 스터디용으로 정리한 내용들입니다 💃  

 

 

👉 이전 강의  

https://ninano1109.tistory.com/189

[모두를 위한 컴퓨터 과학] Ch3. 배열(Array)

 

0) 알고리즘 효율성

• O(n^2): bubble sort, selection sort
• O(n log n): merge sort
• O(n): linear search
• O(log n): binary search
• O(1)

 

1) 검색 알고리즘

• Linear Search
  • 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키며 검사
• Binary Search
  • 정렬 시에만 가능
  • 배열 중간 인덱스부터 시작하여 원하는 값과 비교해서 인덱스의 반복 이동

 

2) 알고리즘 표기법

Big-O(on the order of) 표기법

• 최악의 경우(최대 검색)
• O(n) : linear search
• O(log n) : binary search

Omega 표기법

• 최상의 경우(최소 검색)
• Omega(1) : linear search, binary search

 

3) 선형 검색

• 자료가 정렬되어 있지 않거나, 그 어떤 정보도 없어 하나씩 찾아야 할 경우 유용함
• 따라서 효율성이 매우 떨어짐
• 최악의 상황에서 종료되는 것에 가까움

 

4) 버블정렬

• 두 개의 인접한 자료 값을 비교하면서 위치 교환하는 정렬 방식
• O(n^2): bubble sort
• 정렬이 되어 있는지 여부에 관계 없이(이미 정렬된 것도) 루프를 돌며 비교함
• 따라서, 최소(하한선): O(n^2)

 

5) 선택정렬

• 배열 안의 자료 중 가장 작은/큰 수를 찾아 첫 번째/ 마지막 번째 수와 교환하는 정렬 방식
• 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가함

 

7) 재귀

• 함수가 본인 스스로 호출해서 사용하는 것
• 코드의 간결성과 가독성을 위해서 사용함 => 중첩 루프를 사용하지 않고도 하난의 함수로 동일한 작업 수행 가능

 

8) 병합 정렬

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식
• 재귀적으로 구현
• 상한 시간: O(n log n)
• 숫자들을 반으로 나누기: O (log n) * 반으로 나눈 부분들 다시 정렬 후 병합: O(n) = O(n log n)

 

---

 

next 👉  

https://ninano1109.tistory.com/195

[모두를 위한 컴퓨터 과학] Ch5. 메모리(Memory)