W4 note

• O(n) ←→ Ω(n)

• upper bound : 상한, key보다 큰 첫번째 위치 (초과)를 반환

  원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정

• lower bound : 하한, key보다 크거나 같은 첫번째 위치 (이상)을 반환

  원하는 값 k 이상이 처음 나오는 위치를 찾는 과정

 

• 선형탐색(Linear Search), 버블정렬(Bubble sort), 선택정렬(Select Sort), 병합정렬(Merge Sort)

• 선형 탐색 :

  평균적으로 선형 검색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있습니다.

  선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용합니다.

  이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적입니다.

  ⇒ 정렬이 필요한 이유!

• 버블 정렬 :

  버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.

  버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.

  이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.

  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)=n^2−3n+2

  O(n^2)

  Ω(n^2)

  가장 효율적인 경우 : 정렬이 되어있지 않을 때

  가장 비효율적인 경우 : 이미 정렬되어있을 때

• 선택 정렬 :

  For i from 0 to n–1 Find smallest item between i'th item and last item Swap smallest item with i'th item

  n + (n-1) + (n-2) ... = n(n-2)/2

  O(n^2)

  Ω(n^2)

• 병합 정렬 :

  원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.

  그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽습니다.

실행시간의 상한

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

실행시간의 하한

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

순차적으로 정렬되어 있을 경우, 선택정렬보다 버블 정렬의 하한( Ω(n) )이 낮다.