반복문 시간 복잡도

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

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인 등비수열로 생각할 수 있다.

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

📌 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의 값이 될 수 있는지를 나타낸 수이다.

댓글 공유

자료구조

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합이다.

어떤 비즈니스 로직을 처리할 때 가장 효과적인 자료구조를 찾아서 쓰는 것이 중요하기 때문에 자료구조를 명확하게 알아야한다.

자료구조를 설명하기 위해 C++은 이해하기 쉬운 언어이기 때문에 자료구조 공부는 C++로 할 것이다.

1
2
3
4
5
6
7
8

#include <bits/stdc++.h> // 1
using namespace std; // 2
string a; // 3
int main(){ // 4
    cin >> a; // 5
    cout << a << '\n'; // 6
    return 0; // 7
}

1. 헤더 파일. import할 때 사용한다. bits/stdc++.h 는 모든 표준 라이브러리를 의미한다.

2. std라는 네임스페이스 사용하겠다. cin, cout 사용할 때 원래는 std::cin처럼 네임스페이스 달아서 사용해야하는데 이를 기본으로 설정한다는 뜻이다.

3. 문자열 선언. <타입> <변수명> 이런식으로 선언한다. 예를들어 string a = 'Wix' 이렇게 선언했다면, a는 lvalue, Wix는 rvalue라고 한다. lvalue는 추후 다시 사용될 수 있는 변수이고 rvalue는 한 번 쓰고 다시 사용되지 않는 변수이다.

4. 입력. 대표적으로 cin, scanf가 있다.

5. 출력. 대표적으로 cout, printf가 있다.

6. return 0은 프로세스가 정상적으로 마무리 됨을 뜻한다.

int는 4바이트 정수를 사용할 때 사용되는 타입이다. 표현범위는 -2,147,483,648 ~ 2,147,483,647 입니다.

시간복잡도

시간복잡도란, 입력 크기에 대해 어떤 알고리즘이 실행되는데 걸리는 시간이다. 직접적인 시간을 측정하는 것이 아닌 주요 로직의 반복횟수를 중점으로 측정된다.

왜냐하면 직접적인 시간은 여러가지 요인에 따라 변경될 수 있기 때문이다.

1
2
3
4
5
6
7
8
9
10
11

for(int i = 0; i < 10; i++){
    for(int j =0; j < n; j++){
        for(int k = 0; k < n; k++){
            if(true) cout << k << '\n';
        }
    }
}

for(int i = 0; i < n; i++){
    if(true) cout << i << '\n';
    }

위 코드에서 시간 복잡도는 10n^2+n이다.

빅오표기법(Big - O)

빅오표기법은 복잡도에 영향을 가장 많이 끼치는 항의 상수인자를 제거하고 나머지 항을 없애서 복잡도를 표기하는 표기법이다.

앞선 예시를 빅오표기법으로 나타내면 O(n^2)이다.

여기서 영향을 가장 많이 끼친다는 의미는 입력 크기가 커질수록 증가속도가 가장 큰 것을 의미한다.

예를 들어 n^2은 1,4,9,16,25 이런식으로 증가하는데, n은 1,2,3,4,5 이런식을로 증가하기 때문에 영향이 가장 큰 n^2 항의 상수 인자를 제거하여 빅오표기법으로 나타낸 것이다.

빅오표기법 차트는 외워두자!

n! > 2^n > n^2 > nlogn > n > logn > 1 순입니다.

상수시간 시간복잡도 O(1)

상수시간 시간 복잡도는 입력 크기와 상관없이 일정한 시간복잡도를 가지는 것을 말한다.

1. 입력과 출력

1

cin, cout, scanf, printf

2. 곱하기

1

a[2] *= 2;

3. 간단한 비교 if 문

1
2
3

if (a[0] == 2) {
    // 로직
}

4. 배열 인덱스 참조

1
2

int a[3] = {1,2,3};
int b = a[2]

댓글 공유