빅오 표기법
-
빅오 표기법 (O, big-O)Algorithm & Data Structure 2021. 2. 23. 16:55
빅오란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다. 빅오는 점근적 실행 시간을 표기할때 가장 널리 쓰이는 수학적 표기 방법이다. 여기서 점근적 실행 시간이란 간단하게 n이라는 입력값이 무한대로 커질떄의 실행 시간의 추이를 의미한다. 따라서 충분히 큰 입력값에서의 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 점근적 실행 시간을 달리 말하면 "시간 복잡도"라 할 수 있다. 시간 복잡도의 사전적 정의 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 빅오 표기법인 것이다. 빅오로 시간 복잡도를 표현할때는 최고차항만 표기힌다. 4n^2 + 3n +4 ==> O(n^2) 최고 차항만 표기 한다 -> O..