(TIL) C++ 알고리즘 분석

알고리즘의 분석은 원시 연산의 개수를 세는 것에서 시작한다. 원시 연산이란 다음을 뜻한다.

• 변수에 값 할당
• 함수 호출
• 산술 연산 수행
• 두 값 비교
• 배열에 인덱싱
• 객체 참조
• 함수값 반환

이런 원시 연산들이 몇 번이나 일어나는지를 세는 것으로 실제 수행 시간을 측정하는 것을 대신할 수 있는데 문제는 데이터의 유형에 따라 같은 코드도 실행 시간이 달라진다는 것이다. 그러면 쉽게 생각해서 평균적인 횟수를 구하면 되겠지만 그렇게 하려면 확률 분포를 사용해서 구해야 하기 때문에 어렵다. 그래서 ‘최악’의 경우를 구한다.

Big-Oh 표기법

Big-Oh 표기법은 어떤 함수 f(n)이 있을 때 이것이 n이 증가함에 따라 O(g(n))인 함수 g(n)보다 점근적으로 작거나 같다는 것을 의미한다. 보통 표기할 때 최고차항의 계수는 떼고 표기한다.

Big-Omega 표기법과 Big-Theta 표기법

둘 모두 점근적 표기법으로 전자는 f(n)이 g(n)보다 크거나 같다는 것이고 후자는 f(n)과 g(n)의 증가율이 같다는 것이다.

오늘은 여기까지….. 대체적으로 예시가 많아서 읽고 이해하는 데 시간이 오래 걸렸지만 내용 자체는 크게 많이 없었다. 내일은 C++로 스택, 큐, 그리고 Double-ended 큐를 구현하는 법에 대해서 공부할 것이다.