빅오(Big-O) 표기법
본 포스팅은 빅오(Big-O) 표기법이 필요한 이유를 알고리즘 성능 분석 측면으로부터 점근적 표기법 필요성까지 순차적으로 접근하여 빅오(O), 빅오메가(Ω), 빅세타(Θ) 표기법에 대한 내용까지 다룬다. 다만 알고리즘 성능 척도로 주로 시간 복잡도를 활용하기 때문에 공간 복잡도는 다루지 않는다. 알고리즘의 분석 알고리즘 분석은 정확도에 대한 정확성 분석1과 효율성에 대한 성능 분석2으로 나눌 수 있다. 성능 분석은 다시 시간(속도)적인 측면과 공간(메모리)적인 측면으로 구분할 수 있다. 이것을 시간적 성능, 공간적 성능이라 칭하고 싶으나 성능(Performance)은 컴퓨터 시스템의 사양이나 프로그래밍 언어에 따라 수준의 차이가 나기 때문에 일정하지 않다. 따라서 이러한 조건에 관계없이 항상 일정한 기준으로 분석하기 위하여 복잡도(Complexity)라는 용어를 사용한다. ...