빅오표기법이 뭐지?
빅오표기법은, 알고리즘의 효율성을 표기해주는 표기법을 말한다. 그렇다면 알고리즘의 효율성은 뭘까?
크게 두가지로 나눌 수 있다.
1. 시간 복잡도
2. 공간 복잡도
시간 복잡도는 알고리즘의 시간 효율성, 공간 복잡도는 알고리즘의 공간 즉 메모리의 효율성을 의미한다.
그렇지만 요즘에는(?) 공간 복잡도에 대한 중요성이 떨어져 시간 복잡도를 구체적으로 살펴보자. 사실 빅오 표기법 = 시간 복잡도 나타내는 표기법 이라고 봐도 무방할 듯.
시간 복잡도?
시간 복잡도, 시간 효율성은 곧 알고리즘을 수행하기 위해 필요한 연산의 횟수를 의미한다.
즉, 시간 복잡도가 커진다 ⇒ 연산의 횟수가 늘어난다 ⇒ 실행 속도가 오래 걸릴 것!!
반대로 시간 복잡도가 낮아지면 ⇒ 실행해야 하는 연산의 횟수 줄어듬 ⇒ 이는 효율적인 알고리즘이 될 것이다.
시간 복잡도가 낮은 알고리즘 ⇒ 효율적인 알고리즘
빅오표기법
수학적 정의
빅오값이 클수록 (그래프가 위를 향할수록) 시간이 오래걸리기 때문에 비효율적.
