자료구조(C언어 활용)-01(1)

1~n의 합계를 구하는 세 가지 알고리즘이 있다. 이 각각의 알고리즘이 걸리는 시간을 구하고 장단점을 파악한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// O(1) 알고리즘
long long algorithm_A(int n) {
    return (long long)n * (n + 1) / 2;
}

// O(n) 알고리즘
long long algorithm_B(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

// O(n^2) 알고리즘
long long algorithm_C(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < i; k++) {
            sum += 1; // 원래 sum = sum + i 였는데, O(n^2)에 맞게 sum = sum + 1 로 변경
        }
    }
    return sum;
}

int main(void) {
    clock_t start, finish;
    double duration;
    long long sum;

    int test_cases[] = { 1000, 5000, 10000 };
    int num_cases = sizeof(test_cases) / sizeof(test_cases[0]);

    printf("=======================================================================\n");
    printf("|    n 값   |   알고리즘 A (합, 시간 ms)   |   알고리즘 B (합, 시간 ms)   |   알고리즘 C (합, 시간 ms)   |\n");
    printf("=======================================================================\n");

    for (int i = 0; i < num_cases; i++) {
        int n = test_cases[i];

        // Algorithm A 실행 시간 측정
        start = clock();
        sum = algorithm_A(n);
        finish = clock();
        duration = (double)(finish - start) / CLOCKS_PER_SEC * 1000; // 밀리초(ms) 단위 변환
        printf("|  %6d  |  %10lld, %8.3f ms  |", n, sum, duration);

        // Algorithm B 실행 시간 측정
        start = clock();
        sum = algorithm_B(n);
        finish = clock();
        duration = (double)(finish - start) / CLOCKS_PER_SEC * 1000;
        printf("  %10lld, %8.3f ms  |", sum, duration);

        // Algorithm C 실행 시간 측정
        start = clock();
        sum = algorithm_C(n);
        finish = clock();
        duration = (double)(finish - start) / CLOCKS_PER_SEC * 1000;
        printf("  %10lld, %8.3f ms  |\n", sum, duration);
    }

    printf("=======================================================================\n");

    return 0;
}

 

<결과 화면>

 

 

 

 

📌 알고리즘 B와 C에서 +1과 +i 차이 분석

---

🔹 알고리즘 B (O(n))

long long algorithm_B(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum = sum + i;  // 1부터 n까지 더함
    }
    return sum;
}

✅ 설명:

• sum = sum + i는 1 + 2 + 3 + ... + n을 계산하는 코드.
• 1부터 n까지 숫자를 한 번씩만 더함 → O(n)

✅ 예제 (n = 5일 때)

sum = 0
sum = 0 + 1 = 1
sum = 1 + 2 = 3
sum = 3 + 3 = 6
sum = 6 + 4 = 10
sum = 10 + 5 = 15

출력 결과: 15 (1 + 2 + 3 + 4 + 5)

---

🔹 알고리즘 C (O(n^2))

long long algorithm_C(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < i; k++) {
            sum = sum + 1;  // 1씩 증가
        }
    }
    return sum;
}

✅ 설명:

• sum = sum + 1을 i번 반복하는 for문이 존재
• 전체적으로 1을 여러 번 더함
• i = 1이면 1번 실행, i = 2이면 2번 실행 … i = n이면 n번 실행
• 즉, 1 + 2 + 3 + ... + n 번 sum = sum + 1이 실행됨
• 반복 횟수가 O(n^2)이므로 느림

✅ 예제 (n = 5일 때)

sum = 0
(i=1) sum = sum + 1 → 1회 실행 → sum = 1
(i=2) sum = sum + 1 → 2회 실행 → sum = 3
(i=3) sum = sum + 1 → 3회 실행 → sum = 6
(i=4) sum = sum + 1 → 4회 실행 → sum = 10
(i=5) sum = sum + 1 → 5회 실행 → sum = 15

출력 결과: 15 (1 + 1 + 1 + 1 + 1 + 1 + … n번 실행됨)

---

📌 차이점 정리

알고리즘 B (O(n)) 알고리즘 C (O(n^2))

연산 방식	sum = sum + i	sum = sum + 1
반복문 구조	단일 for문	이중 for문
실행 횟수	n번 실행	1+2+3+...+n번 실행
시간 복잡도	O(n)	O(n^2)
결과 값	n*(n+1)/2	n*(n+1)/2
속도	빠름	느림

✅ 핵심 차이점:

• 알고리즘 B는 sum = sum + i를 사용하여 한 번만 합산
• 알고리즘 C는 sum = sum + 1을 여러 번 반복 (즉, 더하는 연산이 O(n^2)로 증가)
• 결과 값은 동일하지만, 알고리즘 C는 훨씬 느림

📌 결론:
알고리즘 B는 O(n), 알고리즘 C는 O(n^2), 즉 B가 훨씬 효율적! 🚀