그냥 게임개발자
시간복잡도연습 한 번 더 본문
#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이 되는겁니다.
끄읕
'내 개인적인 공부' 카테고리의 다른 글
가장 먼 노드 BFS 알고리즘 (0) | 2024.03.28 |
---|---|
스픽 4일차 - Be동사 간단한질문 (0) | 2024.03.19 |
스픽3일차 - Be동사 부정문 (0) | 2024.03.18 |
스픽 2일차 - be동사 (0) | 2024.03.14 |
스픽 1일차 (2) | 2024.03.12 |