Lecture 11

• How Fast can we sort?

  • 우리는 lower bound를 제공받으면 이게 최대로 빨리할 수 있는 시간이다.
  • 비교 정렬은 Ω(nlogn)이 최대이다. 정렬 알고리즘에서의 최고로 빠른 시간이다.

• Decision Trees

  • n!을 나타내는 값이 리프노드로 존재하는 트리

  

  • comparison sort와 비슷한 방식으로 작동함
  • decision trees를 통해서 Ω(nlogn)번은 비교를 해야 정렬할 수 있다!는 걸 알아냄
  • decision tree가 비교 정렬의 일반화 이런 의미같음

• Corollary ⇒ 따라오는 정리 : Heapsort, Merge sort = O(nlgn) → Θ(nlgn)이된다!

• Counting Sort (↔ comparison sort 비교하여 정렬하는 방법)

  • 선형적인 시간으로 정렬할 수 있을까?

    • 기본적인 아이디어 : x라는 요소는 x보다 작거나 같은 요소들의 수를 알고 있다고 생각하자 → n-1개가있다 ⇒ 나는 인덱스 번호가 n이구나!

    

    이러한 조건을 만들고, 다음과 같이 작동함

    

    실제 수도 코드는 다음과 같다. 왜 뒤에서부터 하는가? → Stable sort의 특성 유지를 위해

    

    • 총 시간은 O(n+k)
      • k = O(n) → 총 시간도 O(n) (비교 정렬이 아니기때문에 O(nlgn)이 아니다!)

  • Radix sort 기수정렬 based on counting sort → stable sort

    • 자릿수별로 정렬하는 방법 (일의 자리, 십의 자리, 백의 자리..)
    • 시간복잡도 = O(n)

Lecture12

• Medians 중앙값

  • i번째로 작은 요소 = ith order statistic
  • minimum, maximum 찾는 방식

  

  일반적인 상황에서의 비교횟수는 n-1 *2 가 되어 2n-2가 되지만, 아이디어를 사용하여

  ai와 ai+1을 비교하고, min, ai 을 비교, ai+1, max를 비교 → 총3번의 비교인데 2개씩묶으므로

  비교횟수가 3n/2로 줄어든다

• Randomized Selection 내가 찾고자 하는 숫자를 찾는 방법

  • 파티션을 통해 찾는 아이디어

  

  피벗의 위치보다 앞에 있으면 앞의 subarray에 대해 재귀함수로 구현, 뒤에 있으면 뒤의 subarray에 대해서 재귀함수 구현!!

  • Worst case : 0/n-1로 나뉘는 경우 → O(n^2)

  • Best case : O(n)

    • 앞에서 배운 파티션이랑 똑같음

  • Avg case

    

    

    

    이걸 계산해주면,

    

    나와서 O(n)이다.

    • 기본적으로 한쪽으로 치우친 형태가 아니어야한다. 0/n-1처럼

• Medians 을 이용해 원하는 값을 찾는법

  

  • 전체 데이터를 5개묶음으로 조를 만든다.

    • 5개 묶음 데이터 중에서 median 중간값을 찾는다.

      • 그 중간값을 기준으로 조를 오름차순으로 정렬한다.
      • 오름차순으로 정렬된 조에서 확실하게 더 작은 값과 큰 값을 알 수 있다. (밑그림참고)

      

      따라서 다음과 같은 예시를 통해 이해해볼수 있다.

      

      

      점선으로 박스쳐진 곳을 보면, 가장 작은 값들, 가장 큰값들이 위치해있다.

      • 러닝 타임 계산

      

      

      따라서 O(n)이다!