시간복잡도연습 한 번 더

#include <iostream>

using namespace std;

int number;

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

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

이것을 보면 시간복잡도만 결론으로 이야기하면 O(logN)입니다.

 

log는 알 거라고 생각하고 이야기 할게요.

 

만약 number가 32라고 칩시다.

그러면 solve에서 더해주는 게

32 + 16 + 8 + 4 + 2 + 1입니다.

그러면 총 5번을 하게 되죠?

그러면 이 log를 써봅시다.

밑이 2인 log2(32)는? 5죠

지수는 32인거구요.

그래서 log2(N)인데 상수또한 빼주어서 총 시간 복잡도는 logN이 되는겁니다.

 

끄읕