BigOTest

#include <iostream>

using namespace std;


int arr[100];
int cnt;

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

void main()
{
    int number;
    cin >> number;

    for (int i = 0; i < number; ++i)
    {
        arr[i] = i + 1;
    }
    
    int sum = SumAdd(0, number - 1);
    
    cout << sum << '\n';
    cout << "cnt : " << cnt << '\n';

    return 0;
}

 

자 우리는 재귀함수를 통해서 1 ~ n까지 더하는 재귀함수를 만들었습니다.

코드 설명은 넘어가구요.

오늘 약간의 꼼수라고 보면 될 것 같네요.

 

이 결과물은 number에 따라 다른데, 만약 number가 5라면 결과값은 15와  cnt는 9라는 숫자가나옵니다.

그렇다면 10을 입력하면 55와 19라는 숫자가 나옵니다.

 

그러면 여기서 시간 복잡도는 얼마로 예상할 수 있나요?

cnt를 보면 얼마나 반복했는지 알  수 있는데

무언가 조금 보이긴 하네요.

9랑 19

입력값은 5와 10

(5*2) - 1 = 9

(10 * 2) - 1 = 9

오호

그러면 결국

n*2-1이네요.

여기서 상수를 지워서

O(n)으로 말할 수 있겠습니다.

끄으틍