재미있는 시간 복잡도 구해보기
사실 대학교 강의 알고리즘에서 모두 해봤던 것이다.
하지만
코딩테스트란 무엇인가?
운동과 마찬가지로 꾸준히 해야 성장을 할 수 있다는 것.
작년여름까지 열심히 백준을 풀었지만 손을 놓고있었기에 아마 많이 잊어버렸을 것이다ㅠ 개념만 아는 정도..
그렇기에 우선 문제를 풀기 전 뇌를 말랑말랑하게 해줄 수 있는 재미있는 시간 복잡도를 구해보자.
일단 시간 복잡도란 무엇인가?
시간복잡도
말 그대로 시간의 복잡도이다!
사실 이렇게 말하면 약팔이 같으니..
시간 복잡도란 "어느 로직(알고리즘)에 얼마나 시간이 걸리느냐?" 라고 말 할수 있을 것이다...
뭐 예를들어 for(반복문)이 있다고 쳐보자.
아래는 C++ 중첩 반복문 코드이다.
### 예시
for(int i = 0; i < 10; i++){
for(int j =0; j < n; j++){
for(int k = 0; k < n; k++){
if(true) cout << k << '\n';
}
}
}
for(int i = 0; i < n; i++){
if(true) cout << i << '\n';
}
위에 코드를 보면 들여쓰기 맨 안쪽에 있는 for문은 n번, 두번째 for문은 n번 첫번째 for문은 10번이 반복된다.
맨 아래 for문 은 n번! 즉 n번 반복이 된다 라고 볼 수 있다.
두번째는 n번! 즉 말 그대로 n번 반복이 된다 라고 볼 수 있다.
맨 위에는 10번! 말 그대로 10번이 반복된다.
그렇다면 위의 로직은 n*n*10 번이 반복된다.
10n^2 라고 볼 수 있다.
맨 아래 반복문은 n번 반복된다.
그럼 방금 반복회수에 n번을 더하면 10n^2+n 번 반복이 된다 라고 볼 수 있다..
쉽죠?
빅오 표기법으로 표기를 해보면
가장 연산에 영향을 미치는 항만 표기한다. => n^2
풀이같은 경우 학교 알고리즘 수업이 아니니.. 귀납적 증명법으로 하지 않겠다.
사실 코테볼때 귀납적 증명법으로 시간복잡도를 구해서 코딩하는 사람은 없을테니..
시간 복잡도 연습 1
이 코드의 시간 복잡도는?
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
int a = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
a += i + j;
}
}
cout << a << '\n';
return 0;
}
정답: O(n^2)
풀이:
첫번째 for문 반복회수 = n
두번째 for문 반복회수 = i = 1/2n 이라고 볼 수 있습니다.
도합 반복회수는 1/2n^2
빅오표기법 => O(n^2)
사실 도합 반복회수까지 생각하지 않고 냅다 빅오표기법으로 생각해서 풀면 for문 두개인데 반복횟수가 상수가 아니고 첫 for문의 i를 갖다 쓴다? => n^2이넹 이라고 생각했다.
시간 복잡도 연습2
짠
#include<bits/stdc++.h>
using namespace std;
int N, M;
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(){
cin >> N >> M;
solve(N, M);
return 0;
}
정답: O(n+m)
풀이: 첫번째 for문 반복회수 N번, 두번째 for문 반복회수 M번 즉, O(n+m)
시간 복잡도 연습3
재귀함수가 등장했다. 과거 학교 알고리즘 퀴즈때 recursion tree 그리면서 점화식으로 시간복잡도 증명한것이 기억이 난다..
#include<bits/stdc++.h>
using namespace std;
int n, a[1004], cnt;
int go(int l, int r){
if(l == r) return a[l];
int mid = (l + r) / 2;
int sum = go(l, mid) + go(mid + 1, r);
return sum;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
a[i - 1] = i;
}
int sum = go(0, n - 1);
cout << sum << '\n';
}
/*
입력
10
출력
45
*/
정답: O(n)
풀이: go라는 함수는 자기 자신을 호출하며 두개로 나뉘어진다. 이것은 recursion tree형태로 나타낼 수 있는데... 그건 이제 첨부하기 너무 귀찮다..
디버깅을 하며 n을 호출할시 얼마나 go 함수를 호출했는지 볼 수 있는데 n이 2일땐 3번, n이 3일땐 5번, n이 4일땐 7번 즉 2n-1이라고 생각할 수 있다.
시간 복잡도 연습4
여기까지만 해야징
#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;
}
정답: O(logN)
풀이: 일단 이 코드의 시간복잡도를 구하려면 log가 뭔지 알아야한다.. 옛날에 교수님이 log의 성질을 모르면 무조건 알고리즘 수업 F 맞는다고 했었는데...
solve함수를 보면 정수 N을 받아 정수 i에 초기화를 시킨 후 while문을 돌리며 받은 i값을 i가 0보다 크다면 나누기 2를 하는것을 볼 수 있다.
즉, 받은 i값은 2로 계속 나누어진다. 예를들어 i가 16이면 16 -> 8 -> 4 -> 2 -> 1 이런식으로.. 즉, 2^4 -> 2^3 -> 2^2 -> 2^1 -> 2^0 라고 볼 수 있다.
지수적으로 감소하고 있기에 log2^n+1 로 볼 수 있다. 여기서 +1은 최종적으로 2^0은 1이 나오기 때문에^^ 저 식에 16을 대입해 계산하면 5가 나온다.
즉, O(logN) 이라고 볼 수 있다.(log 앞에 2는 뺸겁니당)