시간 복잡도

 

 

표기법: 자료구조, 알고리즘 성능 표시 위해서

공간 복잡도: 메모리를 얼마나 많이 차지하는가 -> 메모리 성능이 올라감에 따라 실제로는 잘 사용하지 않음
시간 복잡도: 시간이 얼마나 걸리는가

1) Big-O(빅오): 최악의 경우 / 많이 사용 
2) Big Theta(빅 세타): 최악 = 최선
3) Big-Omega (빅 오메가): 최선의 경우 / 잘 쓰지 않음

 

이제 빅오 표기법을 예시를 통해서 알아보자

for(let i=0;i<n;i++){
	//실행구문
}

이때  i가 n번 반복하므로 시간 복잡도는 O(n)이 된다

 

 

이제 이중for문의 경우를 알아보자

for(let i=0;i<n;i++){
	//실행구문
    for(let j=0;j<n;j++){
		//실행구문
	}
}

이때  i가 n번 j가 n번 반복하므로 시간 복잡도는 O(n^2)이 된다

 

만약 이때, 안쪽 반복문이 1씩 증가하는게 아니고 곱하기나 나누기처럼 배수로 증감하는 경우는 어떻게 표시할까?

이때는 O(nlog n)이 된다.

 

데이터의 총 개수는 n으로 표기한다

 

성능은 아래 순서대로 효율적이라고 판단한다
O(1) > O(log n) > O(n) > O(n log n) > O(n^2) > O(n^3) > O(2^n) > O(n!)

 

* 항상 O(n log n) > O(n^2) 일까?

n이 커지면 차이가 유의미하겠지만 n이 작으면 오히려 후자가 좋은 경우도 있다

 

*O(n) vs O(2n)

n과 2은 n이 커질수록 차이가 무의미해지기 때문에 2는 생략한다 즉, 계수는 생략 가능한다

결론: 자료구조마다 성능이 다르기때문에 효율적인 자료구조를 찾아서 적용해야한다

 

앞으로 자료구조는 모두 자바스크립트로 작성될 예정이다