시간복잡도 직접 디버깅하는 법

cnt 변수 값으로 메인 로직의 반복 횟수를 확인합니다.

#include <bits/stdc++.h>
using namespace std;

int n, cnt;

int main() {
    cin >> n;
    int a = 0;
    for(int i=0; i < n ; i++){
        for(int j=0 ; j < i ; j++){
            a += i + j;
            cnt ++;
        }
    }
    cout << a << '\n';
    cout << "cnt : " << cnt << '\n';
    return 0;
}

3
6
 cnt : 3

4
18
cnt : 6

5
40
cnt : 10

6
75
cnt : 15

 

시간이 남으면 cnt 변수 값의 패턴을 기반으로 점화식을 만듭니다.

#include <bits/stdc++.h>
using namespace std;

int n, a[1004], cnt;

int go(int l, int r) {
    cnt++;
    if (l == r) return a[l];
    int mid = (l + r) / 2;
    int sum = go(l, mid) + go(mid + 1, r);
    return sum;
}

int main() {
    cin >> n;
    for (int i=1 ; i<=n ; i++) {
        a[i-1] = i;
    }

    int sum = go(0, n-1);
    cout << sum << '\n';
    cout << "cnt : " << cnt << '\n';
}

10
55
cnt : 19

5
15
cnt : 9

 

 

log는 지수함수의 역함수라는 점을 유의합니다.

#include <bits/stdc++.h>
using namespace std;

int N, cnt;

void solve(int N) {
    int a = 0, i = N;
    while (i > 0) {
        a += i;
        i /= 2;
        cnt ++;
    }
    cout << a << '\n';
    cout << "cnt : " << cnt << '\n';
}

int main() {
    cin >> N;
    solve(N);
    return 0;
}

32
63
cnt : 6

16
31
cnt : 5

 

재귀함수 = Main Logic X {함수 호출}

 

보통 재귀함수는 순차적으로 go(idx - 1), go(idx + 1) ... 구조입니다.
보통 호출이 2번 일어나면 2의 n제곱, 3번 일어나면 3의 n제곱이라고 보면 됩니다.
다만 이런 구조를 가지지 않은 함수의 경우 다른 시간복잡도를 가집니다. ex) go(idx / 2) 로 호출

 

n=3 일 경우 (1 + 3 + 3^2 + 3^3) 이므로 총 40번 호출됩니다.

#include <bits/stdc++.h>
using namespace std;

int N, cnt;

void solve(int N) {
    cnt++;
    cout << cnt << '\n';
    if (N == 0) return;
    for(int i=0 ; i<3 ; i++) {
        solve(N-1);
    }
    return;
}

int main() {
    cin >> N;
    solve(N);
    return 0;
}

3
40