[2023-09-22] TIL - 시간 복잡도

시간 복잡도는 자료구조와 알고리즘을 배우기 위해 필요한 지식이다.

 

시간 복잡도

프로그램의 성능을 측정하기 위해서는 

- 입력 크기

- 하드웨어 성능

- 운영체제 성능

- 컴파일러 최적화

- 비동기 로직

- 등등..

위와 같이  많은 것들을 고려해야한다.

따라서 프로그램의 성능을 정확히 파악하는 것이 불가능하다.

 

그래서 빅오표기법을 만들어냈다.

 

 

빅오표기법

O(1) < O(log N) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

이를 다른이름으로도 부른다.

상수형 < 로그형 < 선형 < 로그선형 < 2차형 < 지수형 < 팩토리얼형

 

 

O(n)

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

 

O( log n )

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

 

O(n log n)

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

 

O(n2)

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

 

이후의 시간복잡도는 되도록 사용되어서는 안되는 시간복잡도이므로 작성하지 않았다.

 

 

 

 

여기서 아래와 같은 식에 계수가 있거나 상수가 있는 경우는 찾아볼 수 없을 것이다.

O(n²+ 126), O(3n - 30), O(3 log n)  -> O(n²), O(n), O(log n)

 

이유로

빅오표기법은 점근적표기법을 따르기 때문이다.

 

점근적표기법은 함수의 증감 추세를 비교하는 방법이라고 한다.

 

c와 n₀은 양수라고 가정한다. n이 n 을 넘어설 떄 함수 f(n)은 함수 g(n)에 가까워질 수 는 있지만 넘을 수 없다.

한마디로 함수 g(n)은 함수 f(n)의 한계치라고 할 수 있다.

이것을 점근적표기법으로 나타낸 것이 빅오표기법(시간복잡도)라고 얘기한다.

 

 

빅오표기법의 법칙

 

계수 법칙

- n이 무한에 가까울 수록  상수 k의 크기는 의미가 없어진다.

// 두 루프는 같은 O(n)으로 표기된다.
for(let i = 0; i < n; i++){
	...
}

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

 

합의 법칙

- 빅오끼리는 더해질 수 있다.

// 두 루프는 합쳐 O(n + m)으로 표기할 수 있다.
// 계수 법칙에 의해 5는 사라진다.
for(let i = 0; i < n; i++){
	...
}

for(let i = 0; i < m * 5; i++){
	...
}

 

곱의 법칙

- 빅오끼리는 곱해질 수 있다.

// 두 루프를 곱해 O(n^2)으로 표기할 수 있다.
// 계수 법칙에 의해 5는 사라진다.
for(let i = 0; i < n; i++){
	for(let i = 0; i < n * 5; i++){
		...
	}
}

 

다항 법칙

- f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

//다음 루프는 O(n^3)으로 표기할 수 있다.
for(let i = 0; i < n * n * n; i++){
	...
}