WHITEPAEK Tech Docs

Total : 1,085,165 Today : 58 Yesterday : 446

알고리즘 분석 (Algorithm analysis)

알고리즘 분석 (Algorithm analysis)

시간 복잡도 분석 (Time complexity analysis)

✐ 알고리즘의 실행 시간 효율성 분석

✓ 알고리즘의 실제 수행시간을 측정하는 방법 : 실행환경의 영향이 크다.

✓ 시간복잡도 분석은 명령문의 실행 횟수를 분석한다.


✐ 실행시간은 입력(Input)에 따라 달라진다.

✓ 입력크기가 클수록 증가한다.

✓ 동일한 입력 크기라도 입력 사례에 따라 달라질 수 있다.


✐ 입력 크기(Input size) : n으로 표시한다.

✓ 검색 혹은 정렬 문제 : 배열에 속한 원소(Element)의 수

✓ 피보나치 수열 혹은 팩토리얼 계산 : 입력을 부호화하는데 필요한 비트 수 =  logN + 1


✐ 시간복잡도 분석은 입력 크기에 따른 실행시간을 중요, 연산의 수행 횟수로 계산

✓ 입력 크기에 따른 연산의 수행 횟수가 일정하지 않는 경우는 주로 최대 실행 횟수 혹은 평균적 실행 횟수를 고려한다.

✓ 주로  T(n)으로 표기, 최대 실행 횟수는 W(n), 평균 횟수는 A(n)으로 표기


복잡도 카테고리 (Complexity category)

✐ 시간 복잡도의 최고차항의 상수를 무시하고 표시하는 것, Big-O 표기법



(Example)

✐ 입력 크기 n과 상관없는 상수시간 : O(1)

sample1(A[1...n])

  k = [n/2];

   return A[k];

=> T(n) = c = O(1)


✐ 단순 반복(Simple iteration)은 반복 횟수에 비례하는 시간이 소요

sample2(A[1...n])

  tmp = 0;

  for i = 1...n // for문은 n에 비례하는 시간이 소요

    if(A[i]>0)

      tmp += A[i];

  return tmp;

=> T(n) = n + 2 = O(n)


✐ 중첩 반복(Nested iteration)의 경우, 먼저 내부 반복(Inner loop)의 횟수를 계산 후 이에 대하여 외부 반복(outer loop) 횟수를 계산

sample3(A[1...n])

  sum = 0;

  for i = 1...n

    for j = 1...i

      sum = sum + A[i] + A[j];

  return sum; 

=> T(n) = n(n+1)/2 = O(n^2)


✐ 단순 반복처럼 보이지만, 실제는 중첩 반복인 경우

sample4(A[1...n])

  sum = 0;

  for i = i...n

    k = A[1...i]의 최대값; // i에 비례하는 시간 소요되는 반복 연산

    sum += k;

  return sum; 

=> T(n) = n(n+1)/2 = O(n^2)


✐ 두 개 이상의 반복이 연속되는 경우, 차수가 더 높은 반복의 차수가 전체 차수가 됨

 sample5(A[1...n])

  sum1 = 0;

  for i = 1...n // n에 비례하는 시간 소요

    sum1 += A[i];


  sum2 = 0;

  for i = 1...n // n^2에 비례하는 시간 소요

    for j = i ... n

      sum2 = sum2 + A[i] + A[j];

  return sum1 + sum2;

=> T(n) = O(n) + O(n^2) = O(n^2)


✐ 반복의 횟수가 일정 비율로 줄어드는 경우, 차수는 로그(logarithmic)

sample6(A[1...n])

  j = n;

  while(j >= 1)

    A[j]를 출력;

    j = [j/2]; 

=> T(n) = O(log_2 n)

✓ n = 2^5이라고 가정하면, j = 2^5, 2^4, ..., 2, 1이므로 반복횟수는 6번

✓ n = 2^k (<=> log_2 n)이라고 가정하면, j = 2^k, 2^(k-1), ..., 2, 1이므로 반복회수는 (k+1)번


References. 2017 알고리즘 강의 <0장. 알고리즘 기초> - 강영경 교수




✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!

(확인 수정하도록 하겠습니다~^^)


✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!

(지식을 공유해주세요~^^)

댓글(0)