2024 - 02 - 12 C++ 코딩테스트 10주완성 D+4

*시간복잡도

입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됨.


*빅오표기법

복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법

예) 10n^2 + n 을 빅오표기법으로 나타내면 => 
상수 인자인 10을 빼고 핵심인 n^2 만 빼내 O(n^2) 로 표현

영향을 많이 끼치는 항에 대한 기준은 입력값에 대해서 증가속도가 더 빠르고 많은 항이 기준이다.


*빅오표기법 입력값에 대한 증가속도 순서
n! > 2^n > n^2 > n log n > n > log n , 1

*상수시간 시간복잡도

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

시간복잡도 첫번째 예제 실습코드 

int main()
{
    int n;
    cin >> n;
    int a = 0;
    for (int i = 0; i < n; i++) // n = 3이면 0 , 1, 2 
    {
    for (int j = 0; j < i; j++) // n-1 만큼 돌고 
    {
    a += i + j;
    }
    }
    cout << a << '\n';
    return 0;
}

입력받은 n 값이 5일때 기준으로 반복문의 경우를 작성해보면

i = 1 일때, j = 0

i = 2 일때, j = 0,1

i = 3 일때, j = 0,1,2

i = 4 일때, j = 0,1,2,3 이다.

이를 그래프로 그려보면

사각형의 넓이를 구하는 공식은 가로 x 세로 이기때문에 4 x 4 에다 절반이므로 2로 나눠준다.

 j 의 조건문 값이 i 를 포함하지 않는 미만이므로 n값을 빼준다.

따라서 시간복잡도는 1/2(n^2 - n) 이다.

빅오표기법으로 나타내면 상수제외 및 입력값 비례 증가속도가 가장빠른 n^2을 가져오므로 O(n^2) 이다.

시간복잡도 두번째 예제 실습코드

 

void solve(int N, int M)
{
    int a = 1;

    for (int i = 0; i < N; i++)
    {
    a *= i;
    }

    for (int j = 0; j < M; j++)
    {
    a *= j;
    }

    cout << a << "\n";
}

int main()
{
    //Solve 함수에 대한 인자로 받을 지역변수
    int N, M;

    cin >> N >> M;
    solve(N, M);
    return 0;
}

이 경우에는 반복문끼리 덧셈하면 시간복잡도를 구할수 있다.

N 값과 M 값 만큼 반복문을 따로 돌리므로

시간 복잡도는 N + M 이 된다.

만약 하나의 반복문이 아닌 N^2 + N + M^2 + M 같은 여러가지 반복문이 따로 돌고 있을 경우. 
하나의 반복문에서 입력값에 비례해 가장 증가속도가 큰 값을 따로구해 빅오표기법으로 표현한다.

N 값의 경우 가장 증가속도가 큰 값은 N^2 이고 , M 값의 경우 가장 증가속도가 가장 큰값은 M^2 이므로 두값을 더해서 표기한 O(N^2 + M^2) 으로 표현하면 된다

시간복잡도 세번째 예재 실습코드

 

//시간복잡도 세번째 예제
int thirdn, thirda[1004], cnt;

int go(int l, int r)
{
    cnt++;

    if (l == r) return thirda[l];
    int mid = (l + r) / 2;
    int sum = go(l, mid) + go(mid + 1, r);
    return sum;

}

int main()
{
    //시간복잡도 세번째 예제
    cin >> thirdn;
    for (int i = 1; i <= thirdn; i++)
    {
    thirda[i - 1] = i;
    }
    int sum = go(0, thirdn - 1);

    cout << sum << '\n';

    return 0;
}

재귀함수의 경우에는 Cnt 라는 호출마다 증감되는 전역변수를 이용하여

호출이 얼마나 되는지 구해본 뒤, 시간학습도에 대한 식을 추론하여도 됌.

입력값 N에 5 일 경우 9 , 10 일 경우 19이므로

 2n-1 이라는 시간복잡도를 추론할 수 있다.

다른 값을 넣었을 때도 충분히 도출이 가능하기 때문에 시간복잡도는 2n-1 이 되고

이를 빅오표기법으로 하면 상수항을 제외한 O(n) 이 된다.