알고리즘의 수행 시간(기초 사항)

알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요 되는지로 표현한다.

sample1

sample1(A[], n)
{
    k = ⌊n/2⌋;
    return A[k];
}

n/2를 계산하는 것과 A[⌊n/2⌋]값을 리턴한다. 입력 배열의 크기 n에 상관없이 일정한 시간(상수 시간)이 소요된다.

sample2

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

for 루프를 제외한 나머지 부분은 상수시간이 소요되므로 for 루프가 시간을 지배한다. for 루프는 n번 반복되고 각 루프에서는 단순한 덧셈만 하므로 상수 시간이 소요되어 for 루프 관련 수행 시간은 n에 비례한다. 따라서 알고리즘 수행 시간은 n에 비례한다.

sample3

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

배열 A의 모든 원소 쌍을 곱한 합을 구하는 알고리즘이다. for 루프가 n x n = n^2 번 반복되고 각 루프에서는 덧셈 한 번과 곱셈 한 번, 즉 상수 시간 작업이 수행된다. 그러므로 알고리즘의 총 수행 시간은 n^2에 비례한다.

sample4

sample4(A[],n)
{
    sum <- 0;
    for <- 1 to n
        for j <- 1 to n {
           1) k <- A[1...n]에서 임의로 ⌊n/2⌋개를 뽑을 때 이들 중 최댓값; 
            sum <- sum + k;
        }
    return sum;
}

for 루프를 n^2번 반복하면서 매번 배열에서 반을 임의로 뽑아 그 중 최댓값을 계속 더하는 알고리즘이다. 크기가 n인 배열에서 ⌊n/2⌋개를 뽑으면서 이들 중 최댓값을 구하는 것은 n/2에 비례하는 시간이 든다. 이것은 n에 비례하는 시간이다. 즉 1)을 수행하는 데 n에 비례하는 시간이 든다. 전체적으로 for 루프의 반복 횟수와 1)의 수행 시간이 시간을 좌우하므로 총 수행시간은 n^2 x n = n^3에 비례한다.

sample5

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

배열 A에서 i < j인 모든 원소 쌍을 곱을 합산하는 알고리즘이다. for 루프의 총 반복 횟수는 (n-1)+(n-2)+y+2+1 = n(n-1)/2 이 되어 n^2에 비례한다.

sample6

factorial(n)
{
    if(n=1) return 1;
    return n * factorial(n-1);
}

재귀적으로 계속 호출되는 경우에는 함수 factorial()이 총 몇 번 호출되는지가 시간을 좌우한다. factorial()의 총 호출 횟수는 n이다.