시간복잡도 예제

Q4. 다음 코드의 시간복잡도는? 

tip. 로그(log)는 지수 함수의 역함수이다. 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다고 볼 수있다.

 

#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;
}

// 디버깅 작업했을 때
// 입력 32
// 횟수 6
// 입력 8
// 횟수 4

위 코드를 보면 solve 함수 내에 while 문을 사용한 알고리즘이 몇 번 반복하는지가 시간복잡도를 결정하는 핵심 알고리즘이라는 걸 알 수 있습니다. 

cnt 를 선언하고 디버깅했을 때 (logn)+1 임을 알 수 있습니다. 이를 빅오 표기법으로 나타내면 O(logn) 입니다. 

 

 

Q5. 다음 코드의 시간복잡도는? 

#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 => 40번 호출

 

 

보통의 재귀함수는 순차적으로 go(idx -1), go(idx +1)... 이라는 구조를 가지기 때문에 보통은 호출이 두 번 일어나면 2^n, 세 번 일어나면 3^n 이라고 보면 되지만, 저라한 구조를 가지지 않은 함수의 경우 다른 시간 복잡도를 가지기도 합니다. (예) go(idx/2) 으로 호출되는 등.. )

 

그러니까 일반적인 재귀함수는 실행 한번당 몇 번 호출되느냐에 따라서 O(호출되는 횟수^n) 으로 시간복잡도를 갖게되는 경우가 많다. 기억하자.