반복문 시간 복잡도

다음 코드의 시간 복잡도를 구해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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
}

처음에는 하나씩 콘솔을 찍어보면서 계산해보자.

  1. i = 0, j는 무시;
  2. i = 1, j = 0
  3. i = 2, j = 0,1
  4. i = 3, j = 0,1,2

정사각형의 한 변의 길이가 n일 때, 정사각형의 넓이는 n^2이다.

이와 마찬가지로 시간복잡도도 해당 도형의 넓이로 구할 수 있다.

위 식을 넓이로 나타내면 j는 i를 포함하지 않고 있기 때문에 n * (n - 1) % 2로 나타낼 수 있다.

재귀함수 시간 복잡도

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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';
}

시간복잡도는 어떤 로직이 몇 번 반복되었는지를 식으로 만들고 빅오표기법으로 표현하는 것이다.

좀 더 자세히 말하면 재귀함수의 메인로직 * 몇번 호출되는지이다.

그래서 해당 go 함수가 몇번 호출되는지 직접 손코딩으로 그려보며 세어보았다.

n = 5일 때, 9가 나오고 n = 10일 때, 19, n = 20일 때, 39가 나오는 것을 보고 아 시간 복잡도가 2n - 1이구나라는 것을 알게되었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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;
}

예를 들어 n = 3일 때, 처음 1회 실행되고 함수가 3번씩 호출되는데 만약 N이 0이아니면 또 3번씩 호출되므로 공비가 3인 등비수열로 생각할 수 있다.

따라서 등비수열의 합식이 성립한다.

time complexity

📌 Tip

함수 하나가 호출될 때 이 함수가 4번 호출된다면 => 4^n

함수 하나가 호출될 때, 이 함수가 2번 호출된다면 => 2^n

로그 지수 역함수의 시간 복잡도

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std; int N;

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

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

위 식에서 while문은 log N + 1의 시간복잡도를 가지고 빅오표기법으로 나타내면 log N이다.

log N은 2를 몇번 곱해서 N의 값이 될 수 있는지를 나타낸 수이다.