공간적 효율성
시간적 효율성
효율성을 뒤집어 표현하면 복잡도가 됨. 복잡도가 높을수록 효율성은 저하됨
⇒ 시간적 효율성은 주로 입력 크기 n에 대한 연산 횟수로 나타낸다.
복잡도의 점근적 표기
시간 또는 공간 복잡도는 입력 크기에 대한 함수로 표기
→ 이 함수는 주로 여러 개의 항을 가지는 다항식임. 이를 단순한 함수로 표현하기 위해 점근적 표기 (Asymptotic Notation)를 사용
O-표기는 복잡도의 점근적 상한을 나타냄
복잡도가 f(n) = 2n² - 7n + 4 이라면, f(n)의 O-표기는 O(n²)
먼저 f(n)의 단순화된 표현은 n²
단순화된 함수 n²에 임의의 상수 c를 곱한 cn²이 n이 증가함에 따라 f(n)의 상한이 된다.
(단, c > 0)