Today Yurim Learned

# 칸아카데미 알고리즘 강의

https://ko.khanacademy.org/computing/computer-science/algorithms

# 이진 검색

# 수도 코드

  1. min = 0 이고 max = n-1 입니다. 2.max < min, 이라면 멈춥니다. 타겟이 배열에 존재하지 않습니다. -1을 반환합니다.
  2. 'guess'를 'max'와 'min'의 평균으로 계산하고 (정수가 될 수 있도록) 내림합니다.
  3. 배열[guess]가 타겟과 같다면 멈춥니다. 찾았습니다! guess를 반환합니다.
  4. 만약 추측이 너무 낮았다면, 즉 배열[guess] < 타켓이라면, min = guess + 1로 바꿉니다.
  5. 그렇지 않다면 추측이 너무 높습니다. max = guess - 1로 바꿉니다.
  6. 2단계로 돌아갑니다.

# 코드

var doSearch = function(array, targetValue) {
  var min = 0;
  var max = array.length - 1; //24
  var guess;
  while(min<=max) {
      guess = Math.floor((max+min)/2);
      println(guess);
      if(array[guess]<targetValue) {
          min = guess+1;
      } else if (array[guess]>targetValue) {
          max = guess-1;
      } else {
          return guess;
      }
  }
  return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result = doSearch(primes, 97);
println("Found prime at index " + result);

Program.assertEqual(doSearch(primes, 73), 20);

# 점근적 표기법

###알고리즘의 실행 시간

  1. 입력값의 크기에 따른 알고리즘 실행 시간
    • 배열 크기 작을수록 추측 최대 횟수도 줄어든다
  2. 실행 시간의 성장률(rate of growth): 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지
    • 6n^2 + 100n + 300이란 알고리즘에서 n값이 커질수록 6n^2는 나머지 합친것보다 훨씬 기하급수적으로 커진다
    • an^2가 bn+c보다 크고 n이 커질수록 그 차이가 커지는 n의 값(교차점)은 항상 존재
    • 중요하지 않은 항목과 상수 계수를 제거하면 이해 방해하는 불필요한 부분 없어져서 알고리즘의 실행 시간에서 중요한 부분인 성장률 에 집중할 수 있다.

상수 계수와 중요하지 않은 항목 제거했을 때는 **점근적 표기법(asymptotic notation)**을 사용한다. 이는 1. big-Θ 2. big-O 3. big-Ω 3개가 있다.

# 빅 세타 표기법

아래와 같은 선형 검색이 수행되기 위하여 필요한 계산은 c1 * n + c2이다.

  • c1: 루프를 한 번 도는데 드는 시간
  • n: 루프 수
  • c2: guess=0, 마지막 -1리턴 작업 등 추가 시간.

여기서 상수 인자인 c1과 c2를 안다고 해서 실행 시간이 커지는 비율을 알 순 없음. 배열 크기인 n에 따라 커지지. 이는 n의 빅 세타, 혹은 n의 세타 라고 읽는다.


var doLinearSearch = function(array) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // 찾은 경우
    }
  }
  return -1;  // 찾지 못한 경우
}

이진 검색의 실행 시간은 Θ(log n). n이 두배씩 커질때마다 연산 수가 하나씩 늘어나니까(2의 2제곱 = 연산 2번, 2의 3제곱 = 연산 3번)

실제로 상수 인자와 낮은 차원의 항목은 그냥 생랼. 실행 시간이 6n^2 + 100n + 300 마이크로초라면, 빅-세타 표기법에서는 그냥 Θ(n^2)라고 한다. (계수, 저차원항목, 단위 생략)

# 점근적 표기법 형태의 함수

오름차순으로 정렬된 배열의 최솟값 찾기 => 항상 index 0에 있으므로 알고리즘은 Θ(n^0)시간에 실행된다. 실제로는 Θ(1)라고 씀.

점근적 표기법에서 로그의 밑 값은 상수라면 뭐든 무방. log a n = log b n / log b a 식은 모든 양수인 a, b, n에 대해 성립하기 때문. 그러므로 만일 a, b가 상수라면 log a n과 lo b n은 log b a에 의해서만 달라지고 이는 점근적 표기법에서 무시 가능한 상수값.

무슨말이지?

그러므로 이진검색 최악경우 실행시간은 모든 양수값 a에 대해 Θ(log a b)라고 할 수 있다. 보통 Θ(log n)라고 한다.

점근적 표기법을 사용해 알고리즘 분석시 종종 사용하는 함수 순서가 있다.

  • a < b(둘 다 상수)라면 Θ(n^a)의 실행시간보다 Θ(n^a)가 빨리 커짐.
  • Θ(log n)은 모든 양의 상수 a에 대하여 Θ(n^a)보다 천천히 커짐, 그러나 Θ(1)보단 빨리 커짐

Θ(1) < Θ(log n) < n < Θ(n log n) < Θ(n^2) < Θ(n^2 log n) < Θ(n^3) < Θ(2^n)

그래프 그려보면 좋겠다

# 빅 오 표기법

빅 세타: 실행 시간이 커지는 것을 일정 하한선~상한선 내에서 점근적으로 제한하기 위해. 빅 오: 상한선만 제한하고 싶다

이진검색의 최악경우 실행시간은 Θ(log n)이지만 모든 경우에서 Θ(log n)으로 실행된다고 말할 순 없으니, '실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수 있다(더 빠를 수 있다)'를 말하는건 big-O 모든 경우를 포괄하는 일반적 표현은 이진검색이 O(log n)시간 내에 실행된다라고 표현하는 것이 가장 강력하다.

정확하진 않지만 이진 검색의 상한선은 O(n^2)가 될 수 있다. 하지만 Θ(n^2)는 올바르지 않다.

e.g. log n이 O(log 8 n)이다 == log n이 O(log 8 n)의 점근적 상한선을 가지고 있다 == 충분히 큰 n이 있을 경우 어떤 상수 k에 대해 실행 시간이 최대 k * log 8 n 이라는 것이다. (k를 찾을 수 있으면 성립) == log 8 n은 log n의 빅 오가 될 수 있다

5log8n은 log2n보다 항상 크다! (우리는 k=5를 찾았다) 그래서 O(log8n)은 log2n 이 될 수 있다. log8n은 log2n의 빅오가 될 수 있다. n이 짱 크면 log 8 n이 아무리 커봤자 log n보다 클 수 없다

# 빅 오메가 표기법

빅 세타: 알고리즘이 최소한 어느 정도 걸린다 라고 말하고 싶을 때

실행 시간이 Ω(f(n))라면 n이 충분히 클 때 실행 시간은 어떤 상수 k에 대해 최소 k * f(n)

오메가랑 오랑 세타랑 결국 상/하만 다른거지 같은 값이 나오는거 아닌가?

# 점근적 표기법 퀴즈

# Q1

n^k와 c^n함수 사이의 점근 관계는 무엇일까? (k>=1, c>1)

  1. n^k == O(C^n)
  2. n^k == Ω(C^n)
  3. n^k == Θ(C^n)

# A1

n^k는 다항함수, c^2는 지수함수. 다항함수가 지수함수보다 항상 천천히 증가한다(n의 값이 충분히 클 때).

# Q2

log 2 n 및 log 8 n함수들 사이의 점근 관계는 무엇일까?

# A2

둘 다 밑은 다르지만 다항함수적 증가를 보인다 (log 2 n이 log 8 n보다 빨리 증가(처음엔 낮음)) 근데 log 8 n = 1/log 2 8 * log n 이기 때문에 log 8 n은 단순히 log n에 상수를 곱한 것이라는 걸 알 수 있다. 두 함수가 상수 곱의 차이만 날 때 항상 k를 찾아 상한선을 구할 수 있다.

즉 log 2 n은 O(log 8 n), Ω(log 8 n) Θ(log 8 n) 모두에 해당된다.

  • log n은 O(log 8 n)이다: (n이 충분히 클 때) log 8 n은 최소한 log n보다 크다
  • log n은 Ω(log 8 n)이다: (n이 충분히 클 때) log 8 n은 log n보다는 항상 작다
  • log n은 Θ(log 8 n)이다: (n이 충분히 클 때) log 8 n이 커지는 비율은 log n이다

# Q3

log n ^ log 17및 log 17 ^ log n함수들 사이의 점근 관계는 무엇일까?

# A3

모두 밑(2)이 같은 지수함수. log a^b = b * log a 이기 때문에 두 함수는 동일하다.

# 선택 정렬

# 의사 코드

  1. 가장 작은 카드를 찾아서 첫번째에 있는 카드랑 바꾼다
  2. 그 다음으로 작은 카드를 찾아서 두번째에 있는 카드랑 바꾼다
  3. 배열이 정렬될때까지 반복한다

# 분석하기

  • swap함수는 매번 3줄의 코드가 수행된다 (상수)
  • indexOfMinimun함수는 여기 넘기는 array length만큼 코드가 수행된다.(n번)
    • 길이가 8인 array에서 indexOfMinimum 처음 불리면 8번 계산, 두번째는 7번, 6번...
    • 연산 회수는 8+7+6+...+1 = 36
  • 선택 정렬에 소요되는 총 실행 시간은 3부분
      1. indexOfMinimum
      • 1+2+...+n 이니까 다 더하면 (n+1)(n/2)인데 이는 n^2/2 + n/2 이다. 즉 가장 높은 차수로 Θ(n^2)
      1. swap
      • 상수. Θ(n)
      1. 나머지 루프의 selectionSort 함수(다른 함수 실행, 비교 등)
      • 상수. Θ(n)
  • 즉, 선택 정렬은 Θ(n^2)

# QUIZ

  • 빅 세타를 왜 쓰지? 빅 세타의 정의
  • 빅 세타 그래프 그려보기, 순서 말하기
  • 빅 오와 빅 세타의 차이점

← Code School: Digging into Django →