빅-오 표기법 (Big-Oh Natation), 시간 복잡도(Time Complexity)

 

 

시간 복잡도란?

문제를 해결하는데 걸리는 시간과 입력의 함수 관계

해당 알고리즘이 얼마나 효율적인지 정량화해 나타내는 지표

빅-오 표기법이란?

입력값에 따른 알고리즘의 실행 시간 성장률(시간 복잡도)을 점근적 상한선으로 나타낸 수학적 표기법

 

• 해당 알고리즘의 성능을 나타내기 위해선 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다.
• 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아볼 필요성이 있습니다. 이것을 실행 시간의 성장률(rate of growth)이라 합니다.
• 성장률에서 상수 계수와 중요하지 않은 항목을 제거한 것을 점근적 표기법(asymptotic notation)이라 합니다.

big-Θ

중요한 것은 선형 검색의 최악의 경우의 실행 시간은 배열 크기인 n에 따라 커진다는 것입니다. 여기서 실행시간을 표시하기 위해 사용하는 표기법은 Θ(n)입니다. 이는 그리스어인 "세타"로 "n의 빅 세타 " 또는 그냥 n"의 세타"라고 읽습니다.

특정 실행 시간이 Θ(n)이라고 하는 것은 n이 충분히 크다면 실행 시간이 어떤 상수 k1와 k2에 대하여 최소 k1 n이며 최대 k2 n이 된다는 뜻입니다

big-Θ표기법을 사용하는 것은 실행 시간에 대해 점근적으로 근접한 한계값이 있다고 표현하는 것입니다.

"점근적으로"라는 말을 쓰는 이유는 큰 값의 n에 대해서만 적용되기 때문입니다.

"근접한 한계값"이라는 말은 위, 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 뜻입니다.

big-O

예를 들어 이진 검색 실행 시간 최악의 경우는 Θ(log2​n)이지만, 이진 검색이 모든 경우에 Θ(log2​n)이라고 할 수는 없습니다. 찾고자 하는 값을 첫 번째 추측에 찾으면 어떻게 될까요? 그러면 그 경우 실행 시간은 Θ(1)입니다. 이진 검색의 실행 시간은 절대 Θ(log2​n)이상이진 않지만 더 좋을 때도 있습니다.

"실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미인 점근적 표기법 형태를 사용하는 것이 편리할 수도 있습니다. 이런 경우를 위해 "big-O" 표기법을 사용합니다.

이제 모든 경우에 대해 이진 검색의 실행 시간을 알아낼 수 있는 방법이 생겼습니다. 이진 검색의 실행 시간은 항상 O(log2n)라고 할 수 있습니다.

. 최악의 경우의 실행 시간에 대해는 더욱 상세한 식을 만들 수도 있습니다. 바로 Θ(log2​n)이죠. 그렇지만 모든 경우를 포괄하는 일반적 표현으로는 이진 검색이 O(log2​n) 시간 내에 실행된다고 하는 것이 가장 상세한 표현입니다.

big-Ω

상한선 없이 최소한 어느 정도 걸린다고 해야 할 때도 있을 것입니다. 그럴 때는 big-Ω 표기법을 사용합니다. 여기서 Ω는 그리스 문자 "오메가"입니다.

실행 시간이 Ω(f(n))라면 n이 충분히 클 때 실행 시간은 어떤 상수 k에 대해 최소 k⋅f(n)입니다.

여기서 실행 시간은 "f(n)의 big-Ω"라고 합니다. 점근적 하한선을 표현하기 위해선 big-Ω 표기법을 사용하는데, 그 이유는 점근적 하한선은 충분히 큰 입력 크기에서 실행 시간을 밑에서 제한하기 때문입니다.

 

 

Reference

본문의 내용은 다음 사이트를 개인적으로 요약 정리한 글임을 밝히며 자세한 내용은 다음 사이트를 참조하시길 바랍니다.

https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

점근적 표기법 (개념 이해하기) | 알고리즘 | 칸아카데미

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84