방구석 컴퓨터/방구석 잡지식
시간복잡도(Big-O notation)
Big-O notation 이란? 알고리즘의 시간 복잡도를 나타내며, O(f(n)) 으로 나타낸다. 여기서 말하는 시간 복잡도란 연산의 횟수와 관계가 있다. 알고리즘 내에서 시간 복잡도를 계산할 때에는 단위 연산의 횟수를 기준으로 하는데, 단위 연산이란 정의, 단순 계산, 비교, 출력 등 가장 간단한 연산들을 의미한다. 알고리즘을 작성하는데 가장 중요한 부분은 효율성을 증가시키는 것인데, 시간 복잡도를 알아냄으로써 그것들을 비교할 수 있다. Big-O 의 표기법에는 표준적으로 따라야 하는 법칙들이 몇가지 있다. 1. f(n)이 n에 대한 d차식이면, f(n)은 O(n^d) 이다. 2. 가능한 가장 작은 notation을 사용하여야 한다. ex) O(n^2)도 되고, O(n)도 된다면 가장 작은 O(n)을..
2021. 1. 14. 16:17
