알고리즘과 수행시간 분석

이상민·2021년 3월 9일
0
post-thumbnail

1. 알고리즘이란❓

입력과 출력으로 명시 가능한 문제에 대해 해결 절차를 체계적으로 기술한 것

  • 의사 코드를 사용해 기술한다

1-1. 알고리즘의 평가 기준

  1. 정확성
  2. 수행시간
  3. 사용 메모리
  4. 최적성
  • 이중 수행시간과 사용 메모리로 알고리즘의 효율성을 평가한다

1-2. 알고리즘의 효율성

문제를 해결하는 여러 알고리즘 중 어떤 것이 가장 좋은지 평가하기 위한 척도

  • 알고리즘 수행시간 분석 방법
    i) 직접 구현하여 측정 : 구현 비용이 들고, 실행 환경에 따라 수행 시간이 다를 수 있다
    ii) 기본연산 횟수 계산 : 일반적인 방법으로 비교, 사칙 연산 등으로 분석한다. 구현할 필요가 없고 분석 결과가 환경 독립적이다

1-3. 알고리즘 수행시간 분석의 목적

  1. 수행시간 추정
  2. 시간 내 수행 가능한 최대 입력 크기 추정
  3. 알고리즘의 효율성 비교
  4. 좋은 알고리즘 선택
  • 알고리즘은 입력 크기와 형태에 따라 수행시간이 차이가 난다. 입력에 따른 수행시간 분석을 위해 1) 최악의 경우, 2) 평균적 경우, 3) 최선의 경우로 나눠 분석한다

2. 수행시간 분석

2-1. 수행시간 분석 방법

  • 실제 수행시간은 T(n)으로 표시하고 실행되는 기본연산의 개수는 항상 W(n)보다 작거나 같기 때문에
    T(n) <= W(n) 이다

1. 최악의 경우 수행시간

크기가 n인 모든 가능한 입력에 대해 기본연산 수의 최대값. W(n)으로 나타낸다.

수행 최대시간을 보장하지만, 정확한 수행시간을 제시하지 못한다. 알고리즘 수행시간 기본연산 수 분석은 보통 최악의 경우에 한다

2. 평균적인 경우 수행시간

크기가 n인 모든 가능한 입력에 대해 실행되는 기본연산 수의 평균. A(n)으로 나타낸다

최악의 경우 수행시간보다 실제 수행시간과 유사하지만, 분석이 어렵다

3. 최선의 경우 수행시간

크기가 n인 모든 가능한 입력에 대해 실행되는 기본연산 수의 최소값. B(n)으로 표기

예시 ) 배열에서 최대값 찾기

arrayMax(array, n):
    m = list[0]
    for i = 1 to n-1
        if (m > array[i]) then m = list[i]
	output m
  • 반드시 배열의 2번째 요소부터 마지막 요소까지 n-1번 비교연산을 수행하기에 W(n) = T(n) = n-1이다

2-2. 점근적 분석

시간복잡도 분석. n이 매우 커질 때 수행시간을 증가율에 의해 분석한다.

O(1) < O(logn) < O(sqrt(n)) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n^k) < O(a^n)로 자주 표기한다

1. Big-O (O(f(n))
실수 c와 음이 아닌 정수 n0에 대해 n >=n0인 모든 n에 대해 g(n) <= c f(n)을 만족하는 함수 g의 집합

  • g(n) ∈ O(f(n)). 함수 g는 함수 f보다 빠르게 증가하지 않는다. 기껏해야 f(n)의 비율로 증가하는 함수들이다. n이 커지면 상수는 의미가 없어져 무시한다

  • 따라서 g(n)의 증가율이 logn이라도 O(n^2)에 속한다. 틀린 것이 아니라 정확성이 떨어질 뿐이다.

2. Big-Omega Ω(f(n))
실수 c와 음이 아닌 정수 n0에 대해 n >=n0인 모든 n에 대해 g(n) >= c f(n)을 만족하는 함수 g의 집합

  • 적어도 f(n)의 비율로 증가하는 함수들의 집합. g는 f보다 빠르게 증가한다

3. Big-Theta Θ(f(n))
실수 c1, c2와 음이 아닌 정수 n0에 대해 n>= n0 일때 c1 f(n) <= g(n) <= c2 f(n)을 만족하는 세수 n0, c1, c2가 존재하면 g(n) ∈ Θ(f(n))이다

  • 정확하게 f(n)의 비율로 증가하는 함수들의 집합. g는 f와 같은 정도로 증가한다

2-3. 점근적 분석의 측정

  • 점근적 분석도 수행시간을 측정하는데 기본 연산 수를 기준으로 한다

예시) n개 키를 가진 배열에서 주어진 키 찾기

index = 0
while (index < n and x != array[index]) do
    index += 1
  • T(n) 시간복잡도 : O(n)
  • W(n) 시간복잡도 : Θ(n)

예시2) n이 소수인지 판별하기

i = 2
while (i*i <= n) do
    if (n%i == 0) then
        return True
    i +=1
return False
  • n이 소수가 아니라면 2이상의 정수 p*q로 표현할 수 있다. 따라서, p는 sqrt(n)보다 작거나 같다
  • T(n) 시간복잡도 : O(sqrt(n))
  • W(n) 시간복잡도 : Θ(sqrt(n))
profile
편하게 읽기 좋은 단위의 포스트를 추구하는 개발자입니다

0개의 댓글