자료구조 그룹액티비티7

IT 프로그래밍/자료구조

자료구조 그룹액티비티7

기술1 2024. 12. 15. 09:49

그룹액티비티 1번

int fun1(int n, int data[]) {
    int sum = 0;
    for (int i = 0; i < n; i+=2)  // i는 0부터 n-1까지 2씩 증가
        sum += data[i];  // data 배열의 i번째 요소를 더함
    return sum;
}

1. 반복문:

for (int i = 0; i < n; i+=2)에서 i는 0부터 시작하여 n-1까지 2씩 증가합니다. 즉, 반복문은 i = 0, 2, 4, ..., n-1의 값에 대해 실행됩니다.
만약 n이 짝수라면, 반복문은 n/2 번 실행됩니다. 만약 n이 홀수라면, n/2번 반복하지만 마지막 인덱스는 n-1이 됩니다.
이 반복문은 대체로 약 n/2번 반복되므로, 반복문 내부에서 실행되는 작업은 상수 시간 복잡도를 가지므로, 전체 반복문 시간 복잡도는 **O(n/2)**가 됩니다.

2. 결론:

반복문에서 i가 n에 대해 2씩 증가하므로, 반복 횟수는 대략적으로 n/2번입니다. 이를 점근적 표기법으로 나타내면, **O(n)**이 됩니다.
반복문 내부의 작업은 sum += data[i]와 같은 상수 시간이므로 반복문 전체 시간 복잡도는 **O(n)**입니다.

최악의 경우 시간 복잡도:

따라서 이 함수의 최악의 경우 시간 복잡도는 **O(n)**입니다.

이유:

함수는 n에 대해 i를 2씩 증가시키며 배열을 순회하므로, 최악의 경우 반복문은 약 n/2번 반복됩니다.
반복문 내에서 상수 시간이 걸리는 작업만 수행하므로, 시간 복잡도는 **O(n)**으로 나타낼 수 있습니다.
.

1.2

int fun2(int m, int A[], int n, int B[], int C[]) {
    int i = 0, j = 0, k = 0;

    while(i < m && j < n) {
        if (A[i] < B[j])
            C[k++] = A[i], i++;
        else if (A[i] > B[j])
            C[k++] = B[j], j++;
        else
            C[k++] = A[i], i++, j++;
    }

    while (i < m)
        C[k++] = A[i], i++;

    while (j < n)
        C[k++] = B[j], j++;

    return k;
}

이 while 루프는 배열 B[]의 나머지 요소들을 C[]에 추가합니다. j가 n보다 작을 동안 반복됩니다.
이 루프는 n - j번 반복됩니다. 즉, 첫 번째 루프에서 j가 어느 지점에 있는지에 따라 다르지만, 최대 n번 반복할 수 있습니다.

4. 결론:

첫 번째 while 루프는 min(m, n)번 반복되며, 두 번째와 세 번째 while 루프는 각각 m - i번과 n - j번 반복됩니다.
전체 루프는 각 배열을 한 번씩만 순회하므로, 반복문들의 총 반복 횟수는 m + n번입니다.

따라서 이 함수의 시간 복잡도는 **O(m + n)**입니다.

이유:

이 함수는 두 배열을 순차적으로 병합하는 작업을 수행하며, 각 배열의 요소를 한 번씩만 처리합니다. min(m, n)번의 비교 작업과 m 또는 n번의 나머지 요소를 복사하는 작업이 포함되므로, 전체 작업의 시간 복잡도는 **O(m + n)**입니다.

1.3

double fun3(int n) {
    double sum = 0;
    for (double i = 1.0; i < n; i *= 1.5)  // i는 1.5배씩 증가
        sum += i;
    return sum;
}

1. 반복문:

i는 1.0부터 시작하여 매 반복마다 i *= 1.5로 1.5배씩 증가합니다.
즉, i의 값은 1.0, 1.5, 2.25, 3.375, ... 이렇게 증가합니다.
이 반복문은 i가 n을 초과할 때까지 실행됩니다.

2. 반복 횟수 계산:

i는 1.0부터 시작해서 매번 1.5배씩 증가합니다. 즉, i의 값은 기하급수적으로 증가합니다.
반복문이 끝날 때, i는 n 이상이 되어야 하므로, 반복문의 조건은 i < n입니다.
따라서 i가 n에 도달하려면 다음과 같은 조건을 만족해야 합니다:

1.5k≥n1.5^k \geq n

여기서 k는 반복문의 횟수입니다. 즉, 반복문은 대략적으로 k = \log_{1.5}(n)번 반복됩니다. 이를 근사적으로 **O(log n)**번 반복한다고 할 수 있습니다.

3. 결론:

반복문은 기하급수적으로 증가하는 i에 따라 반복 횟수가 **O(log n)**에 비례합니다.
반복문 내에서 수행되는 sum += i는 상수 시간에 이루어지므로, 전체 시간 복잡도는 **O(log n)**입니다.

최악의 경우 시간 복잡도:

따라서 이 함수의 최악의 경우 시간 복잡도는 **O(log n)**입니다.

이유:

i는 매번 1.5배씩 증가하므로, i가 n에 도달하는 데 필요한 반복 횟수는 **O(log n)**입니다.

1.4

int fun4(int n, int target, int data[]) {
    int count = 0, i = 0, j = n - 1;
    while (i < j) {
        if (data[i] + data[j] == target)   // 두 수의 합이 target과 같으면 카운트 증가
            count++, i++, j--;              // i와 j를 모두 증가/감소
        else if (data[i] + data[j] < target)   // 합이 target보다 작으면 i 증가
            i++;
        else                                  // 합이 target보다 크면 j 감소
            j--;
    }
    return count;
}

1. 반복문:

i는 0부터 시작하고, j는 n-1부터 시작합니다.
반복문 내에서 i와 j는 i++ 또는 j-- 방식으로 이동합니다. 즉, i는 한 번에 오른쪽으로, j는 한 번에 왼쪽으로 한 칸씩 이동합니다.
이 반복문은 i < j인 동안 실행되며, i와 j가 서로 교차하면 종료됩니다.

2. 반복 횟수:

i는 0에서 시작하여 n-1까지 증가하며, j는 n-1에서 시작하여 0까지 감소합니다.
따라서 i와 j가 서로 교차할 때까지 반복되므로, 이 반복문은 **O(n)**번 실행됩니다.

3. 각 반복에서의 작업:

각 반복에서 data[i] + data[j]의 합을 구하고, 이를 target과 비교합니다.
조건에 따라 count를 증가시키거나 i 또는 j를 조정하는 작업이 이루어집니다.
각 반복에서 수행되는 작업은 상수 시간이므로, 반복문 내에서의 작업은 **O(1)**입니다.

4. 결론:

반복문은 i와 j가 서로 교차할 때까지 **O(n)**번 실행됩니다.
각 반복에서 수행되는 작업은 **O(1)**이므로 전체 시간 복잡도는 **O(n)**입니다.

최악의 경우 시간 복잡도:

따라서 이 함수의 최악의 경우 시간 복잡도는 **O(n)**입니다.

이유:

i와 j가 교차할 때까지 각 반복에서 한 번씩만 증가하거나 감소하므로, 반복문은 n/2번 실행되며, 이는 **O(n)**으로 간주할 수 있습니다.

1.5

int fun5(int n, int K, int data[]) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        int result = binary_search(n, data, K - data[i]);
        /*
        이진검색을 수행한다.
        */
        if (result != -1)
            count++;
    }
    return count;
}

1. 반복문:

함수는 i가 0부터 n-1까지 증가하는 for 반복문을 사용합니다. 이 반복문은 O(n) 번 실행됩니다.

2. 이진 검색:

binary_search(n, data, K - data[i])는 배열 data에서 K - data[i]를 이진 검색으로 찾는 함수입니다. 이진 검색의 시간 복잡도는 **O(log n)**입니다.
이진 검색은 정렬된 배열에서 특정 값을 찾을 때 사용하는 알고리즘으로, 각 검색에서 배열을 반씩 나누어 가며 값을 찾기 때문에 O(log n) 시간 복잡도를 가집니다.

3. 총 시간 복잡도:

for 반복문은 **O(n)**번 반복되며, 각 반복에서 이진 검색을 호출합니다.
이진 검색은 O(log n) 시간 복잡도를 가집니다.

따라서, 전체 시간 복잡도는 O(n) * O(log n) = **O(n log n)**입니다.

결론:

이 함수의 시간 복잡도는 **O(n log n)**입니다.

이유:

for 반복문에서 각 반복마다 이진 검색을 호출하고, 이진 검색은 정렬된 배열에서 값을 찾는 데 O(log n) 시간이 걸리므로 전체 시간 복잡도는 **O(n log n)**입니다.

1.7

void fun6(int m, int A[], int n, int B[]) {
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j *= 2) {
            if (A[i] <= B[j])
                break;
        }
    }
}

1. 외부 반복문:

for (int i = 0; i < m; i++)는 m 번 반복됩니다.
따라서 외부 반복문은 O(m) 시간 복잡도를 가집니다.

2. 내부 반복문:

for (int j = 1; j < n; j *= 2)는 j의 값이 1부터 시작하여 매번 두 배씩 증가하는 구조입니다.
이 반복문은 j의 값이 n을 초과할 때까지 반복되므로, j는 1, 2, 4, 8, ..., n까지 증가합니다.
이는 로그 기반 증가 방식이기 때문에 내부 반복문은 O(log n) 시간 복잡도를 가집니다.

3. 최악의 경우:

외부 반복문은 O(m) 번 실행되고, 각 반복마다 내부 반복문은 **O(log n)**번 실행됩니다.
따라서 전체 시간 복잡도는 O(m) * O(log n) = **O(m log n)**입니다.

결론:

이 함수의 시간 복잡도는 **O(m log n)**입니다.

이유:

외부 반복문이 m 번 실행되고, 내부 반복문은 j가 두 배씩 증가하는 구조이기 때문에 **O(log n)**번 실행됩니다. 따라서 최종 시간 복잡도는 **O(m log n)**입니다.

1.8 . 외부 반복문:

외부 반복문은 i가 n에서 시작해서 매번 반으로 줄어들며 반복됩니다 (i /= 2).
즉, i는 n, n/2, n/4, ..., 1로 감소합니다.
i가 반씩 줄어들기 때문에 반복문은 **O(log n)**번 실행됩니다.

2. 내부 반복문:

내부 반복문은 i의 값에 따라 실행됩니다.
각 i에 대해 내부 반복문은 i 번 실행됩니다. 즉, 처음에는 n번, 그 다음에는 n/2번, 그 다음에는 n/4번, ..., 1번 실행됩니다.
내부 반복문을 모두 합치면, n + n/2 + n/4 + n/8 + ...와 같은 형태가 됩니다. 이 시리즈는 **O(n)**으로 합산됩니다.

3. 최악의 경우:

외부 반복문은 **O(log n)**번 실행되고, 각 반복에서 내부 반복문은 총합이 **O(n)**입니다.
따라서 전체 시간 복잡도는 **O(n)**입니다.

결론:

이 함수의 시간 복잡도는 **O(n)**입니다.

이유:

외부 반복문이 **O(log n)**번 실행되지만, 내부 반복문이 매번 실행되는 횟수의 합은 **O(n)**입니다. 결과적으로 전체 시간 복잡도는 **O(n)**입니다.

2번

스택과 FIFO 큐를 배열과 단방향 연결리스트로 구현할 때 각 연산의 시간 복잡도를 분석해보겠습니다. 각 경우에 대해 배열 재할당(array reallocation)은 고려하지 않으며, 원형 배열과 일반 배열로 구현한 경우도 나누어 설명하겠습니다.

1. 스택(Stack)

스택은 LIFO(Last In, First Out) 구조로, 가장 최근에 들어온 요소가 먼저 나옵니다.

배열로 구현한 스택 (일반 배열)

Push (새 항목을 스택에 추가): O(1)
배열의 끝에 항목을 추가하는 연산은 일정한 시간 내에 이루어집니다.
Pop (스택에서 항목을 제거): O(1)
배열의 마지막 항목을 제거하는 연산은 일정한 시간 내에 이루어집니다.

단방향 연결리스트로 구현한 스택

Push: O(1)
연결리스트의 맨 앞에 새로운 항목을 추가하는 연산은 일정한 시간 내에 이루어집니다.
Pop: O(1)
연결리스트의 맨 앞에서 항목을 제거하는 연산은 일정한 시간 내에 이루어집니다.

원형 배열로 구현한 스택

Push: O(1)
원형 배열에서 새로운 항목을 배열의 끝에 추가하는 연산은 일정한 시간 내에 이루어집니다.
Pop: O(1)
원형 배열에서 마지막 항목을 제거하는 연산은 일정한 시간 내에 이루어집니다.

2. FIFO 큐 (Queue)

FIFO 큐는 큐에 들어온 순서대로 항목이 처리되는 구조입니다.

배열로 구현한 FIFO 큐

Enqueue (큐에 항목 추가): O(1)
배열의 끝에 항목을 추가하는 연산은 일정한 시간 내에 이루어집니다.
Dequeue (큐에서 항목 제거): O(n)
배열에서 맨 앞에 있는 항목을 제거하고, 나머지 항목들을 한 칸씩 왼쪽으로 밀어야 하므로 최악의 경우 O(n)의 시간이 걸립니다.

단방향 연결리스트로 구현한 FIFO 큐

Enqueue: O(1)
연결리스트의 끝에 새로운 항목을 추가하는 연산은 일정한 시간 내에 이루어집니다.
Dequeue: O(1)
연결리스트의 맨 앞에서 항목을 제거하는 연산은 일정한 시간 내에 이루어집니다.

원형 배열로 구현한 FIFO 큐

Enqueue: O(1)
원형 배열에서 항목을 큐의 끝에 추가하는 연산은 일정한 시간 내에 이루어집니다.
Dequeue: O(1)
원형 배열에서 큐의 맨 앞 항목을 제거하는 연산은 일정한 시간 내에 이루어집니다.

요약

자료구조연산배열단방향 연결리스트원형 배열

스택 (Stack)	Push	O(1)	O(1)	O(1)
	Pop	O(1)	O(1)	O(1)
FIFO 큐 (Queue)	Enqueue	O(1)	O(1)	O(1)
	Dequeue	O(n)	O(1)	O(1)

결론

스택의 경우, 배열과 단방향 연결리스트 모두 O(1) 시간 복잡도를 가집니다.
FIFO 큐의 경우, 배열로 구현할 경우 Dequeue가 O(n)이 걸리지만, 단방향 연결리스트와 원형 배열로 구현하면 모든 연산이 O(1)로 수행됩니다.

3번

1. 배열: 정렬 안 함

배열이 정렬되지 않았을 때는 배열의 인덱스를 통해서만 데이터를 접근할 수 있습니다.

검색 (search)

배열이 정렬되지 않았으므로, 값을 찾기 위해 선형 탐색을 해야 합니다.

시간복잡도: O(n)
이유: 배열의 모든 항목을 하나씩 확인해야 하므로 최악의 경우 배열 크기만큼 비교해야 합니다.

삽입 (insert)

배열에 항목을 추가할 때, 배열의 끝에 추가하는 경우에는 시간복잡도가 **O(1)**입니다. 하지만 삽입 위치를 찾고 그에 맞게 요소를 밀어내는 작업이 필요할 수 있으므로 최악의 경우에는 O(n) 시간이 걸립니다.

시간복잡도: O(n)
이유: 최악의 경우 배열에서 삽입 위치를 찾고, 그 위치부터 끝까지 값을 밀어내야 하기 때문입니다.

삭제 (remove)

삭제 연산은 먼저 값을 찾고, 그 값이 위치한 곳부터 배열의 뒤쪽 요소들을 하나씩 당겨야 하므로 최악의 경우에는 O(n) 시간이 걸립니다.

시간복잡도: O(n)
이유: 삭제할 값을 찾는 데 시간이 걸리고, 삭제한 후 그 뒤의 모든 요소들을 한 칸씩 당겨야 하므로 최악의 경우에 n번의 이동이 필요합니다.

2. 배열: 오름차순 정렬

배열이 오름차순으로 정렬되어 있으면 이진 검색을 통해 검색을 더 효율적으로 할 수 있습니다.

검색 (search)

배열이 오름차순으로 정렬되어 있으므로 이진 검색을 사용할 수 있습니다.

시간복잡도: O(log n)
이유: 이진 검색은 배열의 중간 요소를 기준으로 탐색 범위를 반으로 줄여가며 찾기 때문에, 최악의 경우에도 탐색 범위가 절반씩 줄어듭니다.

삽입 (insert)

삽입 연산은 먼저 값을 삽입할 위치를 이진 검색으로 찾아야 하고, 그 후에는 O(n) 시간이 걸립니다. 삽입 위치부터 뒤로 데이터를 한 칸씩 밀어야 하기 때문입니다.

시간복잡도: O(n)
이유: 이진 검색으로 삽입 위치를 찾는 데 O(log n) 시간이 걸리지만, 삽입 후에는 그 위치부터 끝까지 데이터를 밀어야 하므로 최악의 경우 O(n) 시간이 걸립니다.

삭제 (remove)

삭제 역시 값을 먼저 찾아야 하고, 삭제 후에는 그 뒤의 모든 요소들을 한 칸씩 당겨야 하므로 최악의 경우 O(n) 시간이 걸립니다.

시간복잡도: O(n)
이유: 이진 검색을 사용하여 값을 찾을 수 있으나, 그 뒤의 요소들을 밀어내야 하므로 O(n) 시간복잡도가 필요합니다.

3. 연결리스트: 정렬 안 함

연결리스트는 포인터로 연결된 요소들을 순차적으로 탐색하므로 배열과는 다르게 메모리 상에 연속적으로 저장되지 않지만, 삽입과 삭제에 유리합니다.

검색 (search)

정렬되지 않았기 때문에 선형 탐색을 해야 합니다.

시간복잡도: O(n)
이유: 연결리스트에서는 순차적으로 요소를 탐색해야 하므로 최악의 경우 모든 노드를 확인해야 합니다.

삽입 (insert)

연결리스트에서는 삽입 위치를 찾을 필요 없이, 새로 삽입할 노드를 그 위치에 연결하면 되므로 O(1) 시간이 걸립니다. (단, 삽입할 위치를 찾는 데 시간이 걸릴 수 있습니다.)

시간복잡도: O(1)
이유: 삽입할 위치를 알고 있을 때는 삽입만 하면 되므로 시간복잡도는 **O(1)**입니다. (하지만 삽입 위치를 찾는 데 O(n) 시간이 걸릴 수 있음)

삭제 (remove)

삭제할 값이 어디에 있는지 찾고, 그 값을 제거해야 하므로 최악의 경우 O(n) 시간이 걸립니다.

시간복잡도: O(n)
이유: 삭제할 값을 찾는 데 최악의 경우 연결리스트를 끝까지 확인해야 하므로 O(n) 시간이 걸립니다.

4. 연결리스트: 오름차순 정렬

연결리스트가 오름차순으로 정렬되어 있으면 검색을 더 효율적으로 할 수 있지만, 삽입과 삭제는 여전히 선형 시간 복잡도를 가집니다.

검색 (search)

정렬된 연결리스트에서는 값을 찾을 때 O(n) 시간이 걸리지만, 순차적으로 값을 확인해야 합니다.

시간복잡도: O(n)
이유: 연결리스트는 랜덤 액세스를 지원하지 않으므로, 여전히 순차 탐색을 해야 합니다.

삽입 (insert)

삽입하려는 위치를 찾는 데 O(n) 시간이 걸리고, 삽입 후에는 연결만 하면 되므로 O(1) 시간이 걸립니다.

시간복잡도: O(n)
이유: 삽입할 위치를 찾는 데 O(n) 시간이 걸리고, 삽입 후에는 연결만 하면 되기 때문입니다.

삭제 (remove)

삭제할 값을 찾는 데 O(n) 시간이 걸리고, 삭제 후 연결만 하면 되므로 O(1) 시간이 걸립니다.

시간복잡도: O(n)
이유: 삭제할 값을 찾고 연결만 하면 되므로 O(n) 시간이 걸립니다.

요약

자료구조검색 (search)삽입 (insert)삭제 (remove)

배열 (정렬 안 함)	O(n)	O(n)	O(n)
배열 (오름차순 정렬)	O(log n)	O(n)	O(n)
연결리스트 (정렬 안 함)	O(n)	O(1)	O(n)
연결리스트 (오름차순 정렬)	O(n)	O(n)	O(n)

결론

배열에서는 정렬되지 않은 경우 선형 탐색이 필요하고, 정렬된 경우 이진 검색을 사용하여 성능을 개선할 수 있습니다. 삽입과 삭제는 배열의 크기만큼 데이터를 밀어야 하므로 최악의 경우 O(n) 시간이 걸립니다.
연결리스트에서는 삽입과 삭제가 O(1) 시간에 가능하지만, 검색은 여전히 선형 탐색이 필요하므로 최악의 경우 O(n) 시간이 걸립니다. 정렬 여부는 성능에 큰 영향을 미치지 않습니다.

4번

주어진 선택지에서 **O(n²)**이 아닌 것은 (2) 21.98입니다.

이유:

(1) 1510 + 12099: 이 식은 상수항들의 합이므로 **O(1)**입니다. 즉, 상수 시간복잡도이며, **O(n²)**가 아닙니다.
(2) 21.98: 이 값은 상수입니다. 상수는 **O(1)**에 해당합니다. 시간복잡도가 n에 의존하지 않으므로 **O(n²)**가 아닙니다.
(3) n³/√n: 이 식을 간단히 계산하면 **n³ / √n = n^(3/2)**입니다. 이는 **O(n^(3/2))**이며 **O(n²)**보다 낮은 차수이므로, **O(n²)**가 아닙니다.
(4) 20^20 * n: 이 식은 20^20이 상수이고, n에 선형적으로 비례하므로 **O(n)**입니다. **O(n²)**보다 낮은 차수이므로 **O(n²)**가 아닙니다.

따라서 (2) 21.98가 O(n²)이 아닌 항목입니다. 이유는 상수이기 때문에 n에 의존하지 않고, 시간복잡도 계산에서 제외되는 값입니다.

5번

주어진 함수들의 점근적 차수를 낮은 것부터 높은 것 순으로 나열해 보겠습니다.

n (선형 시간복잡도)
- 이 함수는 **O(n)**으로, 입력 크기 n에 비례하는 시간복잡도를 가집니다. 점근적으로 가장 낮은 차수입니다.
n log² n (로그 선형 시간복잡도)
- 이 함수는 **O(n log n)**으로, 선형적인 n과 로그 시간복잡도 log n이 곱해진 형태입니다. n에 비례하면서 로그 항목이 더해져서 선형보다는 약간 더 느리지만, 여전히 선형 시간복잡도보다 높지는 않습니다.
n³ (다항 시간복잡도)
- 이 함수는 **O(n³)**로, **O(n²)**이나 **O(n log n)**보다 차수가 큽니다. 이 함수는 입력 크기 n이 커질수록 상당히 빠르게 증가하는 형태입니다.
2^n (지수 시간복잡도)
- 이 함수는 **O(2^n)**로, 지수적으로 증가하는 시간복잡도를 가집니다. 입력 크기 n이 1 증가할 때마다 값이 두 배로 증가하므로, 다른 함수들에 비해 빠르게 증가합니다. 이는 점근적 차수가 가장 높은 시간복잡도입니다.

나열 순서:

n (O(n))
n log² n (O(n log n))
n³ (O(n³))
2^n (O(2^n))

이유:

**O(n)**는 선형 시간복잡도로, 가장 느리게 증가합니다.
**O(n log n)**은 선형보다 빠르지만, 지수적으로 증가하는 것은 아니므로 그 다음으로 낮은 시간복잡도입니다.
**O(n³)**는 다항 시간복잡도로, n이 커질수록 급격히 증가하지만, 지수함수보다는 느립니다.
**O(2^n)**는 지수 시간복잡도로, n이 커질수록 매우 빠르게 증가하므로 가장 높은 점근적 차수를 가집니다.

주어진 함수들:
1. f(n)=2nf(n) = 2^n (지수 함수)
2. g(n)=n3/2g(n) = n^{3/2} (다항식 함수)
3. h(n)=nlog⁡2nh(n) = n \log^2 n (로그-선형 함수)
1. f(n)=2nf(n) = 2^n (지수 함수)
- 이 함수는 지수적으로 증가합니다. nn이 커질수록 급격하게 증가합니다.
- 점근적 복잡도는 **O(2^n)**입니다.
- 지수 함수는 다른 함수들에 비해 매우 빠르게 증가하므로, 이 함수가 가장 큰 복잡도를 가집니다.
2. g(n)=n3/2g(n) = n^{3/2} (다항식 함수)
- 이 함수는 n의 3/23/2 제곱에 비례하는 다항식 함수입니다.
- 점근적 복잡도는 **O(n^{3/2})**입니다.
- 이 함수는 다항식 함수 중에서 비교적 느리게 증가합니다. 다만, nn보다 빠르게 증가하지만 n2n^2보다는 느리게 증가합니다.
3. h(n)=nlog⁡2nh(n) = n \log^2 n (로그-선형 함수)
- 이 함수는 n에 로그의 제곱이 곱해진 형태입니다.
- 점근적 복잡도는 **O(n \log^2 n)**입니다.
- 로그 함수는 다항식보다 증가 속도가 느리지만, 선형 함수보다는 빠르게 증가합니다.
결론: 점근적 차수 비교
- O(2^n) (지수 함수): 가장 큰 시간복잡도
- O(n^{3/2}) (다항식 함수): 중간
- O(n \log^2 n) (로그-선형 함수): 가장 작은 시간복잡도
알겠습니다! 점근적 시간복잡도가 낮은 순서대로 나열하면:

g(n)=n3/2g(n) = n^{3/2}

h(n)=nlog⁡2nh(n) = n \log^2 n

f(n)=2nf(n) = 2^n

따라서, 낮은 순서대로 나열하면:

2 < 3 < 1 입니다.

7번

주어진 문제에서 각 선택지에 대해 하나씩 살펴보겠습니다.

선택지 분석:

(1) f(n)=O(nc)f(n) = O(n^c)이고 g(n)=O(nd)g(n) = O(n^d)일 때, f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)이고 f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)이다.

설명:
- f(n)=O(nc)f(n) = O(n^c)와 g(n)=O(nd)g(n) = O(n^d)에서 c≤dc \leq d일 경우, f(n)+g(n)f(n) + g(n)의 시간 복잡도는 O(nd)O(n^d)입니다. g(n)g(n)이 더 높은 차수를 가지므로, f(n)f(n)의 영향을 무시할 수 있습니다.
- 이 선택지는 옳습니다.

(2) f(n)=O(nc)f(n) = O(n^c)이고 g(n)=O(nd)g(n) = O(n^d)일 때, f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)이고 f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)이다.

설명:
- 이 선택지는 중복된 표현입니다. 위와 같은 이유로 f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)는 정확하지만, 나머지 표현은 중복된 설명입니다.
- 이 선택지는 옳습니다.

(3) f(n)=O(nc)f(n) = O(n^c)이고 g(n)=O(nd)g(n) = O(n^d)일 때, f(n)+g(n)=O(nc)f(n) + g(n) = O(n^c)이고 f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)이다.

설명:
- f(n)f(n)의 시간 복잡도가 O(nc)O(n^c)이고 g(n)g(n)의 시간 복잡도가 O(nd)O(n^d)일 때, c≤dc \leq d이면, f(n)+g(n)f(n) + g(n)는 O(nd)O(n^d)입니다.
- 따라서 이 선택지는 옳지 않습니다. O(nc)O(n^c)가 아닌 O(nd)O(n^d)로 표현해야 합니다.

(4) f(n)=Θ(nc)f(n) = \Theta(n^c)이고 g(n)=Θ(nd)g(n) = \Theta(n^d)일 때, f(n)+g(n)=Θ(nd)f(n) + g(n) = \Theta(n^d)이고 f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d)이다.

설명:
- f(n)=Θ(nc)f(n) = \Theta(n^c)이고 g(n)=Θ(nd)g(n) = \Theta(n^d)일 때, c≤dc \leq d이면 f(n)+g(n)=Θ(nd)f(n) + g(n) = \Theta(n^d)이고, 따라서 f(n)+g(n)=O(nd)f(n) + g(n) = O(n^d) 역시 성립합니다.
- 이 선택지는 옳습니다.

결론:

void merge_sort(int data[], int left, int right) { if (left >= right) return; int mid = (left + right) / 2; merge_sort(data, left, mid); merge_sort(data, mid + 1, right); merge(data, left, mid, right); }

문제: 위 병합 정렬의 시간 복잡도는 무엇인가요?

예상 문제 풀이 (간략)

배열에서 값을 검색하는 시간 복잡도:
- 시간 복잡도: O(n)O(n)
- 이유: 배열을 끝까지 순차적으로 검색하기 때문입니다.
이진 탐색 알고리즘의 시간 복잡도:
- 시간 복잡도: O(log⁡n)O(\log n)
- 이유: 이진 탐색은 배열의 절반을 매번 제거하며 탐색하기 때문입니다.
이중 루프가 있는 코드의 시간 복잡도:
- 시간 복잡도: O(n2)O(n^2)
- 이유: 두 개의 루프가 각각 nn번 반복되므로 시간 복잡도는 O(n2)O(n^2)입니다.
배열에서 특정 값이 존재하는지 확인하는 함수:
- 시간 복잡도: O(n)O(n)
- 이유: 배열을 끝까지 순차적으로 탐색하기 때문입니다.
배열 정렬 후 특정 값 찾기:
- 시간 복잡도: O(nlog⁡n)O(n \log n) (정렬) + O(n)O(n) (탐색) = O(nlog⁡n)O(n \log n)
- 이유: 정렬의 시간 복잡도가 O(nlog⁡n)O(n \log n)이고, 이후 탐색은 O(n)O(n)입니다.
배열에서 두 개의 값의 합이 주어진 값을 만드는지 확인하는 알고리즘:
- 시간 복잡도: O(n)O(n)
- 이유: 두 포인터를 사용하여 한 번의 반복으로 해결하기 때문입니다.
이진 탐색을 사용한 값 찾기:
- 시간 복잡도: O(nlog⁡n)O(n \log n)
- 이유: 외부 반복문이 nn번 반복되고, 각 반복에서 이진 탐색을 수행하기 때문입니다.
재귀를 사용하는 시간 복잡도:
- 시간 복잡도: O(n)O(n)
- 이유: 각 호출마다 n−1n - 1번의 호출을 발생시키며, 총 nn번 호출됩니다.
분할 정복 알고리즘 (Divide and Conquer)의 시간 복잡도:
- 시간 복잡도: O(n)O(n)
- 이유: 재귀적으로 배열을 반씩 나누고, 각 부분에 대해 선형적인 작업을 수행합니다.
재귀 호출이 포함된 병합 정렬:
- 시간 복잡도: O(nlog⁡n)O(n \log n)
- 이유: 분할 후 병합을 하며, 각 단계에서 배열을 전부 병합해야 하므로 전체적으로 O(nlog⁡n)O(n \log n)의 복잡도를 가집니다.

8번

병렬처리(parallel processing)는 여러 프로세서나 코어를 사용하여 하나의 작업을 동시에 처리하는 방식입니다. 이 관점에서 점근적 시간 복잡도(Asymptotic Time Complexity)의 분석을 살펴보면, 병렬화가 알고리즘의 성능에 미치는 영향을 이해하는 데 중요합니다.

1. 병렬화가 시간 복잡도에 미치는 영향

병렬처리의 주된 장점은 동일한 작업을 여러 프로세서에서 나누어 처리함으로써 실행 시간을 줄이는 것입니다. 점근적 시간 복잡도 분석에서는 주로 **빅-오 표기법(O-notation)**을 사용하여 알고리즘의 성능을 평가하는데, 병렬화된 알고리즘의 경우 몇 가지 주요 요소가 시간 복잡도에 영향을 미칩니다.

1.1 작업 나누기(분할)

작업을 병렬로 나누는 방식에 따라 성능 향상 정도가 달라집니다. 예를 들어, 큰 작업을 적당한 크기로 나누어 각 프로세서가 병렬로 작업을 수행한다면, 작업의 분할이 효율적일수록 성능이 향상됩니다.

1.2 작업 간의 의존성

작업들이 서로 의존적일 경우, 병렬화가 성능 향상에 제한을 받을 수 있습니다. 예를 들어, 작업 A가 끝나야 작업 B가 시작될 수 있다면, 병렬 처리로 모든 작업을 동시에 처리할 수 없기 때문에, 작업 간 의존성이 적을수록 병렬화의 효과가 높습니다.

1.3 Amdahl's Law (암달의 법칙)

Amdahl's Law는 병렬화된 시스템에서 전체 성능 향상 비율을 예측하는 데 사용됩니다. 이 법칙은 알고리즘의 병렬화가 불가능한 부분이 있을 경우, 전체 성능 향상에 제한을 준다는 것을 설명합니다. 암달의 법칙은 다음과 같이 표현됩니다:

Sp=1(1−P)+PNS_{p} = \frac{1}{(1 - P) + \frac{P}{N}}

여기서:

SpS_p는 병렬화 후의 성능 향상 비율,
PP는 병렬화 가능한 작업의 비율,
NN은 사용된 프로세서의 수입니다.

따라서, 병렬화가 가능한 부분이 적거나 프로세서 수가 많아질수록 성능 향상은 점차 둔화됩니다.

1.4 로드 밸런싱

병렬 처리에서는 각 프로세서에 할당된 작업량이 균등하게 분배되어야 최적의 성능을 발휘할 수 있습니다. 만약 일부 프로세서가 과도하게 작업을 처리하고 다른 프로세서는 유휴 상태라면, 성능은 오히려 저하될 수 있습니다. 이를 해결하기 위한 로드 밸런싱 기법이 필요합니다.

2. 병렬화된 알고리즘의 시간 복잡도 분석

병렬 알고리즘의 시간 복잡도를 분석할 때는 다음과 같은 접근법을 고려합니다:

2.1 워크와 깊이 분석

**워크(Work)**는 알고리즘이 전체적으로 수행하는 작업의 양을 나타냅니다. 병렬화된 알고리즘의 워크는 일반적으로 병렬화된 알고리즘과 직렬 알고리즘이 동일합니다.
**깊이(Depth)**는 병렬적으로 수행할 수 있는 독립적인 단계들의 수입니다. 깊이가 짧을수록, 즉 병렬화 가능한 작업의 비율이 높을수록, 병렬화의 효과가 극대화됩니다.

2.2 병렬 시간 복잡도

병렬 알고리즘의 시간 복잡도는 보통 두 가지로 나타낼 수 있습니다:

최악의 경우 시간 복잡도: 병렬화가 적용되더라도 여전히 비효율적인 경우.
평균 시간 복잡도: 대부분의 경우에 대해 병렬화된 알고리즘이 어떻게 성능을 향상시키는지 평가하는 방법.

병렬 알고리즘의 시간 복잡도는 다음과 같이 표현할 수 있습니다:

Tparallel=Twork/P+TdepthT_{\text{parallel}} = T_{\text{work}} / P + T_{\text{depth}}

여기서:

TworkT_{\text{work}}는 전체 작업량,
PP는 프로세서 수,
TdepthT_{\text{depth}}는 병렬화 가능한 깊이입니다.

3. 병렬 알고리즘의 예

Merge Sort: 병렬화된 병합 정렬의 경우, 각 분할 작업을 병렬로 처리하고, 병합 단계에서 효율성을 높일 수 있습니다.
Matrix Multiplication: 행렬 곱셈에서는 각 요소에 대해 병렬 작업을 수행하여 계산을 가속화할 수 있습니다.

결론

병렬처리는 작업을 동시에 수행함으로써 알고리즘의 실행 시간을 줄이는 중요한 기법입니다. 그러나 병렬화가 항상 성능 향상으로 이어지는 것은 아니며, 작업의 분할, 의존성, 로드 밸런싱, Amdahl’s Law 등 다양한 요소가 성능에 영향을 미칩니다. 따라서 병렬화된 알고리즘의 점근적 시간 복잡도를 분석할 때는 이러한 요소들을 고려하여 최적화할 수 있는 방법을 찾아야 합니다.

'IT 프로그래밍 > 자료구조' 카테고리의 다른 글

자료구조 예상문제2 - 미로찾기문제 (2)	2024.12.15
자료구조 예상 문제 1 (0)	2024.12.15
자료구조 그룹액티비티 6 (2)	2024.12.15
자료구조 [예상] (0)	2024.10.23
자료구조 과제3 (0)	2024.10.23

현재글자료구조 그룹액티비티7

기술 블로그

string 설명, 티스토리챌린지, 따배시 강의, 백준2284번, 오블완, 빈곤이란, 따배시, 따배시 강의 요약, 백준 10813, 녹색혁명, 빈곤이란 무엇인가?, 거듭제곱 구하는 법, strtok기능, 빈곤의 사회학적 정의, 말레이시아 경제, x5x6, 빈곤의 원인, C++, 프로그래밍 예제, 빈곤 정의,

« 2024/12 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31