Let's measure time complexity by n^3 and 2^n

본 글은 알고리즘 설계 과목에서 작성한 코드를 기반으로 한 글입니다.

 

💡 Time Complexity

알고리즘을 실행하는 데 걸리는 시간을 의미합니다.

 

Q1. n^3을 만족하는 2차 행렬 a, b, c의 곱셈을 기반으로 하는 3중 for loop를 작성하라.

 

#include <iostream>
#include <ctime>

using namespace std;

int main() {
    const int n[] = {10, 50, 100, 150, 200};
    clock_t start, finish;
    double duration;

    for (int i = 0; i < 5; i++) {
        int N = n[i];
        int a[N][N], b[N][N], c[N][N];
        start = clock();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        finish = clock();
        duration = (double)(finish - start);
        cout << "n = " << N << ", time required = " << duration << " ns" << endl;
    }
    return 0;
}

 

Q2. 2^n을 만족하는 피보나치 수열 등 알고리즘을 작성하라

 

#include <iostream>
#include <ctime>

using namespace std;

int Fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n <= 2) {
        return 1;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main() {
    const int n[] = {10, 20, 30};
    for (int i = 0; i < 3; i++) {
        clock_t start, finish;
        double duration;
        int N = n[i];
        start = clock();
        int fib = Fibonacci(N);
        finish = clock();
        duration = (double)(finish - start);
        cout << "n = " << N << ", time required = " << duration << " ns" << endl;
    }
    return 0;
}

 

💡 What I learned

 

컴파일 시간과 실행 시간 중 실행 시간을 직접 출력하며 두 알고리즘을 비교해보았다.

마감이 촉박한 과제였지만 Complexity 계산은 즐거웠다. 좋은 과제였다. ^^