big-oh
-
[ Open Data Structures ] - Asymptotic NotationDataStructure 2021. 5. 5. 21:07
Asymptotic Notation 자료구조를 분석함에 있어서 다양한 작업(Operation)들의 Running time에 대해 논할 때가 있다. 당연히 정확한 Running time은 각각 컴퓨터에 따라 다르게 나타난다. 우리가 어떤 Operation의 Running time에 대해 이야기 할 때는 Operation 도중에 수행되는 컴퓨터의 지시(Computer instructions)의 수를 이르는 것이다. 아주 간단한 코드에서도 이 양[量]은 정확하게 계산해내기 힘들다. 따라서 Running time을 정확하게 계산하는 대신에 우리는 소위 말하는 Big-Oh notation을 사용하기로 한다. 어떤 함수 f(n)에 대해서 O(f(n))은 다음과 같은 함수의 집합을 이르는 것이다. 도표로 생각을 해보..