자료구조 BigO
알고리즘은 어떠한 문제를 해결하기 위한 방법이고, 어떠한 문제를 해결 하기 위한 방법은 다양하기 때문에 방법(알고리즘) 간에 효율성을 비교하기 위해 빅오(big-O) 표기법을 보통 가장 많이 사용한다.
빅오 표기법 (big-O notation) 이란?
빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다. 쉽게 생각하면 알고리즘 스카우터라 생각하면 된다.
알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다. 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.
(시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)
그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.
시간 복잡도 표기법
Big-O(빅 오) 표기법 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법이다. 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용한다.
Big-Ω(빅 오메가) 표기법 알고리즘 최상의 실행 시간을 표기한다.
Big-θ(빅 세타) 표기법 알고리즘 평균 실행 시간을 표기한다.
(핵심은 Big-O는 최악의 실행 시간을 표기한다는 것이다!)
빅오 표기법의 특징
- 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.
이와 같이 상수항은 무시하고 표기한다.
-
영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.
이와 같이 영향력이 지배적인 이외에 영향력이 없는 항들은 무시한다.
빅오 표기법 성능비교
빅오 표기법에서 주로 사용되는 표기법은 아래 그래프들과 같다.
그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다.
(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)
( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )
빅오 표기법 예제
빅오 표기법의 예제는 어떤 것들이 있는지 정도만 외워두고 알고리즘 공부를 해보면서 이해해 나가면 될 것 같다.
단축평가(short-circuit evaluation)
논리곱(&&) 연산자는 두개의 피연산자가 모두 true 로 평가될 때 true 를 반환한다. 논리곱 연산자는 좌항에서 우항으로 평가가 진행된다.
논리합(||) 연산자는 두개의 피연산자 중 하나만 true 로 평가되어도 true 를 반환한다. 논리합 연산자 또한 좌항에서 우항으로 평가가 진행된다.
논리곱 연산자와 논리합 연산자는 논리 연산의 결과를 결정하는 피연산자를 타입 변환하지 않고 그대로 반환한다. 이를 단축 평가라 한다. 단축 평가는 표현식을 평가하는 도중에 평가 결과가 확정된 경우 나머지 평가 과정을 생략하는 것을 뜻한다.
(즉, 그 연산의 결과과 참이 될지 거짓이 될지 최종적으로 결정하는 것이 출력된다. 결정권을 가진 것이 출력된다!)
// 논리곱(&&) 연산자
'a' && 'b' // => 'b'
false && 'b' // => false
'a' && false // => false
// 논리합(||) 연산자
'a' || 'b' // => 'a'
false || 'b' // => 'b'
'a' || false // => 'a'단축 평가를 사용하면 if 문을 대체할 수 있다. 어떤 조건이 true 여야 실행되어야 한다면, 논리곱(&&) 연산자 표현식으로 이를 대체하고, 조건이 false 여야 실행되어야 한다면 논리합(||) 연산자 표현식으로 이를 대체할 수 있다.
let finished = true;
let message = '';
message = finished && '완료';
console.log(message); // => '완료'
finished = false;
message = finished || '미완료';
console.log(message); // => '미완료'