알고리즘...2

알고리즘의 수행 시간

입력의 크기에 대해 시간이 어떤 비율로 소요되는지 표현하는 것을 말한다.

이에 대한 몇 가지 예를 들면 다음과 같다.

 

Code(A[], n)
{
    sum <- 0
    for i <- 1 to n
        sum <- sum + A[i]
    return sum
}

이 코드의 경우 반복문 내부의 작업은 상수 시간만을 소요하기 때문에 전체적인 소요 시간은 반복문에 관련된 n에 비례하게 된다.

 

Code(A[], n)
{
    sum <- 0
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] * A[j]
    return sum
}

또, 위와 같이 배열의 모든 원소 쌍의 합을 구하는 알고리즘의 경우에 중첩된 반복문이 각각 n의 시간을 소요하기 때문에 n * n = n^2의 시간을 소요하게 된다.

 

대부분 이런 식으로 소요시간을 구할 수 있으나 재귀 함수의 경우 자기 호출하는 경우를 생각하지 않으면 상수 시간 호출로 생각되므로 자기 호출한 횟수가 소요 시간을 좌우하게 된다.

 

Code(n)
{
    if (n == 1) return 1
    return n * Code(n - 1)
}

위와 같은 팩토리얼 함수의 경우 단순하게 함수 자체의 소요 시간은 상수 시간이 된다. 하지만 자기 호출하는 경우를 따지면 총 수행 시간은 n에 비례하는 것을 알 수 있다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘