1주차 개념 #2. 빅오표기법(Big - O notation)

1주차 개념 #2. 빅오표기법(Big - O notation)

앞서서 이 코드의 시간 복잡도가 얼마라고 했죠?

이 코드의 시간 복잡도는 주요로직이 반복하는 횟수에다가 중점을 맞춘다고 했죠.

근데 사실은 저희가 이러한 시간 복잡도를 쓰기도 하지만,

이거를 Big-O 표기법이라는 어떤 표기법을 통해서, order 라고 하는 커다란 O, 그리고 이렇게 괄호를 쳐서 이런 식으로 표현을 해요.

10n^2 + n 이라는 이러한 시간 복잡도를 O(n^2)으로 표현을 하는데, 이러한 Big-O 표기법에 대해서 얘기를 해보도록 할게요.

---

빅오 표기법(Big - O notation) 이란, 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법 입니다.

이거를 제가 설명을 해보도록 할게요.

자 여러분 가장 많이 영향을 끼치는 게 뭘까요? 가장 많이 영향을 끼치는 건 뭐냐면 바로 입력 크기가 커지면 커질수록, 증가 속도가 커지는, 그러니까 기울기가 높다라고 하죠.

다시 말해서, 입력 크기가 커지면 커질수록, 증가 속도도 더 빠르게 증가하는 게 바로 가장 영향을 많이 끼치는 녀석이다 라고 합니다.

예를 들어서 우리 입력 크기가 n 이라고 했잖아요.

n이 1, 3, 9, 10 이렇게 커진다 라고 해볼게요. 이렇게 입력 크기가 커진다 라고 했을 때, n 제곱은 어떻게 커지죠? 1, 9, 81, 100 이렇게 커지죠.

n의 증가 속도보다 n^2의 증가 속도가 훨씬 더 빠르죠?

그러면 지금 보시는 것처럼 이게(10n^2) 하나의 항, 이게(n) 하나의 항 이렇게 되는데, 10n^2 항이 조금 더 영향을 많이 준다라고 하는 거예요.

다시 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애는 게 바로 빅오 표기법이라고 했는데, 여기서 영향을 많이 끼친다는 것은 입력 크기가 커지면 커질수록 증가 속도도 많이 증가하는 게 영향을 많이 끼친다 라고 하는 겁니다.

지금 보면, 가장 영향을 많이 끼치는게 10n^2이에요.

그런데 상수인자를 뺀다 라고 했죠.

그래서 이게

O(n^2) (오더 n 제곱) 이렇게 되는 거예요.

자 다시, 가장 많이 영향을 끼치는 그 항을 기반으로 그 항 빼고 나머지는 다 제거하는 거예요.

그 다음 그 항에서도 상수인자를 제거해서 O(n^2) 이렇게 표현하는게 빅오표기법 입니다.

그런데 제가 지금 비교한 것은 n제곱과 n이에요. n제곱과 n을 비교해 가지고 n제곱이 n보다 입력 크기가 커지면 커질수록 증가 속도가 더 크다라고 했는데, 사실은 n제곱과 n말고도 여러가지가 있어요.

이렇게 여러가지가 있는데, 지금 한번 보겠습니다.

지금 보시는 것처럼 이게 Big-O Complexity Chart 라는 거예요. 우리가 가장 많이 영향을 끼치는 항을 매번 이런식으로 1, 4, 9 vs 1, 9, 81 이렇게 값을 넣어서 확인할 수도 있지만, 그러기엔 힘들죠.

그래서 이런 것들을 외워주는 게 좋은데,

지금 보시는 것처럼 n제곱이 n보다 이렇게 증가속도, 기울기가 조금 더 크죠?

근데 이것보다 더 큰 게 있어요. 2의 n승이랑 n! 이건데, 제가 예시를 한번 들어볼게요.

n이 1, 2, 3, 4, 5 이렇게 간다고 해볼게요.

지금은 n 제곱은 제외하고, 2^n 이랑 n! 이거 두 개만 볼게요.

먼저, n!는 자신을 포함해서 그 전까지를 곱하는 거에요. 자 n = 1부터 해서 5까지 해보면,

이렇게 됩니다.

자 2의 n승은 어떻게 되죠?

이렇게 되네요. 자 그러면 여기 중에서 증가 속도가 가장 빠른 건 뭐예요? n!이죠.

근데 여러분 아시겠지만 지금 보시는 것처럼

이렇게 n이 작을 때, 즉 입력 크기가 작을 때는 2의 n승이 클 때도 있죠. 다만 우리가 보는 거는 입력 크기가 커지면 커질수록, 빠르게 기울기가 어느게 더 높냐라는 걸 보는 거죠.

그래서 n!이 더 기울기가 높기 때문에 만약에 이 두 개의 항으로 이루어진

이런 식의 시간복잡도를 가진다고 했을 때, 이거를 Big-O 표기법으로 나타내면,

이게 지워지게 된다는 거예요. 왜? 영향을 가장 많이 끼치는 항, 즉 입력 크기가 커지면 커질수록 증가수가 더 빠른 항은

이거니까 아시겠죠?

다시 빅오 표기법은 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법 입니다.

그리고 이러한 Complexity Chart는 외워 주셔야 합니다.

그러면 우리가 앞서서 설명할 때

제가 이 부분을 뭐라고 했죠? 상수 시간을 가지는 간단한 로직, 상수 시간의 시간 복잡도를 가지는 간단한 로직이다 라고 제가 말씀을 드렸어요.

그런데 이거는 입력 크기가 아무리 증가해도 똑같아요.

예를 들어서 여기서 n이 100에서 이렇게 증가해도,

이 부분은 똑같죠. 입력 시간과 상관이 없죠.

이 부분을 오더 1 이라고 하는 O(1) 이라고 부르기도 하고, 상수 시간의 시간 복잡도를 가진다 라고도 하는, 입력 크기와 상관없이 일정한 시간 복잡도를 가지는 것을 얘기를 합니다.

자 우리 이 부분들은 다 O(1), 상수 시간 복잡도를 가지는 거에요. 외워둡시다.

이러한 연산들 전부 다 O(1), 상수 시간을 갖는 겁니다.