📌 시간복잡도

코딩테스트를 준비하다 보면 테스트케이스에서 꼭 런타임 아웃이 걸리는 경우가 생긴다.
도.대.체. 왜 내 코드만 시간이 오래걸리나 답답했던 경험들이 다들 한번쯤은 있을거라고 생각한다.

시간복잡도는 프로그램의 성능을 가늠하는 척도 중 하나이다.
물론, 이것도 상대적이고 대략적이다.

Big-O notation

빅오 표기법은 위 시간복잡도를 표현하는 하나의 표현법이다.

data 양에 따른 시간 복잡도 그래프이다.

시간 복잡도는 상수 시간 < 로그 시간 < 선형 시간 < 선형로그 시간 < 이차 시간 < 지수 시간 < 펙토리얼 시간 순으로 커진다.

💻 코드로 비교해 보기

O(n) 선형시간

for(let i=0;i<n;i++){
		...
}

O(logn) 로그시간

for(let i=0;i<n;i *= 2){
		...
}

O(nlogn) 선형로그 시간

for(let i=0;i<n;i++){
    for(let j=0;j<n;j*= 2){
		...
    }
}

O(n^2) 지수 시간

for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
		...
    }
}

첨언

당연히 컴퓨터니까 알아서 계산해 주겠지 라고 생각하며 마구 코드 돌리던 나!
반성합니다