📕 참고: 10주완성 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'
if(true) cout << k << '\n'; , if(true) cout << i << '\n'로직이 반복되는 만큼 → 10*n^2 + n
빅오 표기법
복잡도에 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법이다.
10*n^2 + n → O(N^2)
시간복잡도에 가장 영향을 많이 끼치는 입력에 따라 증가속도가 훨씬 큰 n^2만을 표기한다.
영향을 많이 끼치는 복잡도 순서는 n! > 2^n > n^2 > nlogn > n > logn > 1 이다.
상수시간 시간복잡도O(1)
입력 크기와 상관없이 일정한 시간복잡도를 가지는 것을 말한다.
- 입력과 출력
cin,cout,scanf,printf - 곱하기, 나누기, 나머지연산, 빼기
- 간단한 비교 if문
if(a[2]==2) - 배열의 인덱스 참조
int b = a[2];
#include <bits/stdc++.h>
using namespace std;
int n, a[1004], cnt;
int go(int l, int r){
cnt ++ ;
if (l==r) return a[l];
int mid = (l+r)/2;
int sum = go(l,mid) + go(mid+1,r);
return sum;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> n;
for(int i=0; i<n; i++){
a[i-1] = i;
}
int sum = go(0,n-1);
cout<< sum << '\n';
cout << cnt << '\n';
return 0;
}
재귀함수 go가 몇번 실행되는지 확인해보면
n=10일 때 19, n=5일때 9이므로 시간복잡도가 2n-1임을 알 수 있다. 빅오표기법으로 나타내면 상수는 제외하고 가장 영향이 큰 복잡도만 남기므로 O(n)이 된다.
재귀함수의 시간복잡도
재귀함수 메인 로직 * 함수가 몇번 호출되는지(cnt)로 판단한다.
#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() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> N;
solve(N);
return 0;
}재귀함수 solve를 호출하면 1+3+9+27 만큼 반복된다. 등비수열의 합으로 나타낼 수 있으므로 1/2 *(3^n-1)이 된다. 빅오표기법으로 나타내면 O(3^n) 가 된다.
함수 하나당 2번 호출되면? O(2^n)
logic * cnt로 나타낼 수 있다.
공간복잡도
입력 크기에 대해 알고리즘이 실행되는데 필요한 메모리 공간의 양을 의미한다.
int a[1000000];
void f(){
int b[1004];
}
int main(){
}
보통은 배열의 크기를 기반으로 계산한다.
보통의 메모리 제한 int타입 기준
- 64MB : 1500만
- 128MB : 3000만
- 256MB : 6000만
- 512MB : 1억2천만
