Big-O 표기법

정의

어떤 양수 n0, c이 존재할 때 f(n)은 O(g(n))입니다. 이때, n0과 c는 다음을 만족해야 합니다.
n0 이상의 모든 n에 대해 f(n) <= cg(n)

쉽게말해,
n은 O(n)다. n0=1, c=1이기만 해도 n <= n이 만족하므로
2n 역시 O(n)다. n0=1, c=2라면 2n <= 2n이 만족
n은 O(2n)일수도 있다. n0=1, c=1/2면 n <= 1/2*(2n) = n
n이 O(n^2)일 수도 있다 n0=1, c=1이면 n <= n^2이 만족

그러나
n^2이 O(n)일 수는 없다. c가 아무리 크더라도, 언젠가 항상 cn보다 n^2가 클 때가 온다

계수가 아닌 차수가 중요!

예시

시간복잡도

#include <cstdio>
using namespace std;
 
int main(){
    int N, sum = 0;
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
        sum += i;
    printf("%d\n", sum);
}

• 사칙연산은 O(1)로 본다.
• for문이 한 번 돌아가는 데에, i<=N인지 비교하는 연산 한 번, sum에 i를 더하는 연산 한 번, i를 1 증가시키는 연산 한 번 이렇게 최소 3개의 연산이 필요 (3N번의 연산)
• O(3N) == O(N)

#include <cstdio>
using namespace std;
 
int main(){
    int N, sum;
    scanf("%d", &N);
    sum = N*(N+1)/2;
    printf("%d\n", sum);
}

• 이 경우 N에 상관없이 연산은 3번만함
• O(1)

같은 문제라도 어떻게 푸느냐에 따라 시간복잡도가 달라질 수 있다.

공간복잡도

#include <cstdio>
using namespace std;
 
int main(){
    int N, X, A[10000];
    scanf("%d %d", &N, &X);
    for(int i=0; i<N; i++)
        scanf("%d", A+i);
    for(int i=0; i<N; i++)
        if(A[i] < X) printf("%d ", A[i]);
}

• 공간복잡도는 N개의 값을 저장해야 하므로 O(N)

#include <cstdio>
using namespace std;
 
int main(){
    int N, X;
    scanf("%d %d", &N, &X);
    for(int i=0; i<N; i++){
        int A;
        scanf("%d", &A);
        if(A < X) printf("%d ", A);
    }
}

• 이런식으로 입력 받자마자 처리하면 공간복잡도 O(1)

우선도
시간복잡도 > 공간복잡도

_[출처] 빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도|작성자 라이_https://blog.naver.com/kks227/220769859177