개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

 

안녕하세요

 

로스윗의 코딩캠프입니다.

 

오늘도 멋진 개발자가 되기 위해 여기까지 오신 여러분을 응원합니다.

 

오늘은 자료구조와 알고리즘에 이어 빅오표기법에 대한 포스팅을 진행하도록 하겠습니다.

 

모두 팔로 팔로미~

 

 

 

 

 

 

※ 혹시 아직 알고리즘에 대해서 헷갈리시는 분은 이전 포스팅을 참고해주세요 :)

 

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이 #2

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이 #2

 

 

 

 

- 빅오 표기법이란?

이번 시간에는 여러 자료구조와 알고리즘이 존재할 때에

 

각각을 비교하기 위해 점근 표기법중 하나인 빅오 표기법에 대해 알아보도록 하겠습니다.

우리가 집에서 학교에 가는 방법에 대한 알고리즘을 찾는다고 가정을 할 때 

 

여러가지 방법이 있을 수 있겠죠.

 

-걸어가는 방법

- 버스를 타고 가는 방법

- 어딘가를 경유해서 가는 방법

 

등등 수도 없이 많이 있을 것입니다.

모든 방법이 학교에 도착한다는 목적을 달성하기는 하지만
모든 방법이 학교에 가장 빨리 도착하는 방법은 아니겠죠.

 

알고리즘도 마찬가지입니다.

한 가지 문제를 해결하는데 있어서 여러가지 방법들이 있을 수 있겠는데

 

빅오 표기법은 이런 여러 방법들을 시간과 공간 측면에서 비교할 수 있게 도와줍니다.

 

 

※참고※
점근 표기법에는 빅오 표기법 외에도 세타 표기법, 오메가 표기법이라는 것이 있습니다.
하지만 여러분이 앞으로 어떤 개발자와 이야기는 나눌 때 복잡도에 대한 얘기가 나오면 
항상 빅오 표기법을 기준으로 얘기하기 때문에 다른 개념들은 그냥 넘어가셔도 괜찮습니다.

 

 

빅오표기법을 수학적으로 표현하면 아래의 표와 같이 나타낼 수 있습니다.

 

 

 

수학적으로 표현한 빅오표기법

 

 

조금 복잡해 보일 수 있는데요, 그렇지 않습니다.

 

쉬워요.

 

가장 위에 상한 점근이라고 설명하고 있는 부분이 빅오 표기법이고
가운데 하한 점근이라고 설명하고 있는 부분이 오메가 표기법이고
마지막에 상한/하한 점근이라고 설명하고 있는 부분이 세타 표기법입니다.

 

그런데 이렇게 수학적 정의만 보면 잘 와닿지 않죠?
그래서 더 쉽게 설명을 드려보겠습니다.

 

 

 

빅오표기법 그림 설명 예시

 

다음과 같은 그림처럼 7개의 점이 있다고 가정을 하고
우리가 원하는 데이터를 가장 앞칸부터 순서대로 순회하면서 찾는 작업을 수행한다고 해봅시다.

한칸을 수행하는데 걸리는 시간이 0.1초라고 가정을 하고 
만약 우리가 원하는 값이 첫번째 칸에 있다고 한다면 결과를 찾는데 걸리는 시간은 0.1초가 되겠죠.

반대로 우리가 원하는 값이 마지막 칸에 있다고 한다면 0.1초의 7배인 0.7초가 걸리게 됩니다.
그러면 우리는 이 작업을 하는데 걸리는 시간을 얼마라고 표현을 해야 할까요?

가장 짧은 소요시간이 걸리는 제일 앞칸에 데이터가 있는 경우,
어떤 경우라도 이 경우보다는 오래 걸리기 때문에 이것을 하한선이라고 정의합니다.

반대로 가장 상한의 경우는 가장 마지막 칸에 있는 경우겠죠.
어떤 경우라도 이 상한선을 넘어가진 않겠죠.

그리고 마지막으로 이 두 경우의 중간값인 평균값, 이렇게 3가지 경우가 있을 수 있겠습니다.

빅오 표기법은 여기서 가장 상한인 경우를 가정해서 복잡도를 표기를 하게 됩니다.

 

실제로 정확한 소요시간을 알려주는 것은 아니지만 

어떤 경우라도 대략적으로 그 범주 안에는 포함될 것이다 라는 것을 알 수 있는 것이죠.

위의 경우 같은 경우는 데이터의 개수가 늘어날수록 검색에 소요되는 시간이 이제 선형적으로 늘어나겠죠.
5개면 5개라고 표현하겠고 10개면 10, n개면 n이 되기 때문에 5n의 시간 복잡도를 가지게 됩니다.

 

 

 

 

점근 표기법의 특징

 

 

 

- 점근 표기법의 특징

점근 표기법은 여러가지 특징이 있는데 

첫번째는 가장 큰 영향력이 있는 항만 표시한다는 것입니다.

예를 들면 빅오(O)의 N의 3제곱 + N의제곱 + N이 있을 때는 

가장 큰 영향력이 있는 N의 3제곱의 항만 표시를 합니다. O(N3제곱)

두번째는 상수항은 무시한다.
O(2N+1) -> O(N) 이라고 표시를 합니다

 

어렵지 않죠?

 

 

 

빅오의 특징

 

 

- Big-O(빅오)의 특징

 

그 다음으로 빅오끼리의 크기를 비교해보자면

 

O만 떼면 여러분이 아는 크기와 동일하다고 보시면 됩니다.

O의1 < O(logN) < O(N) < O(NlogN) < O(N제곱) < O(2의 N제곱)

이거는 외우지 않아도 직관적으로 알 수 있겠죠.

그리고 우리는 빅오 표기법으로 공간 복잡도와 시간 복잡도를 표현하는데

사실 공간복잡도 보다는 시간복잡도를 주로 사용하게 됩니다.

공간복잡도를 먼저 말씀을 드리자면 

공간복잡도는 데이터 관리에 필요한 공간을 나타내는 개념이라고 보시면 되겠습니다.

그래서 데이터의 양이 증가하거나 감소하면 공간이 어떻게 변하는지를 표현할 수 있게 해주는거죠.

프로그램을 작성할 때는 예상되는 공간을 측정할 수 있게 도와주는 지표가 됩니다.

공간복잡도가 데이터 관리에 필요한 공간을 나타내는 개념이었다면

시간복잡도는 데이터 처리에 소요되는 시간을 나타냅니다.

마찬가지로 데이터의 양이 증가함에 따라서 시간이 얼마나 걸릴지를 표현할 수 있기 때문에
프로그램의 에상 처리 시간을 예측해 볼 수 있습니다.

앞에서 말씀드린것처럼 

 

공간복잡도 보다는 시간 복잡도를 훨씬 더 중요하게 다룹니다.

 

공간복잡도가 덜 중요하다기 보다는

 

컴퓨터의 메모리 공간이 과거에 비해서 굉장히 크게 늘어났기 때문에

메모리 문제에 대해서 과거만큼 신경을 쓰지 않는 부분도 있고,

우리가 어떤 프로그램을 쓰더라도 일단은 속도가 느리면 만족도가 떨어지잖아요.

사용자 입장에서는 아무리 좋은 프로그램이라도 속도가 느리면 쾌적하다고 느끼기 어렵기 때문에

많은 개발자들이 시간복잡도를 통해 실행 시간을 줄이기 위해 굉장히 많은 노력을 합니다.

시간 복잡도가 높으면 프로그램의 속도가 느려지는 원인이 된다고 예측을 할 수 있고

나중에 지연 장애가 발생했을 때

 

-왜 발생 했고

-어디서 발생했는지를 

찾을 수 있는 근거가 된다고 볼 수 있습니다.

 

시간복잡도는 중요하기 때문에

 

다음 포스팅에서는 시간 복잡도에 대해서 조금 더 자세히 다뤄보도록 하겠습니다.

 

여기까지 읽으신 여러분은 이미 성공한 개발자!!

 

모두 다음 포스팅에서 만나요~

 

로~스윗!!