[Algorithm] 2) 시간복잡도, Big-O 표기법 (1)

 저번 장에서 알고리즘의 필요성에 대해 언급하면서, 이러한 알고리즘의 성능의 기준이 되는 '시간복잡도(Time Complexity)에 대해서 잠깐 설명을 했다.

 

https://humanwater.tistory.com/4

[Algorithm] 1) 알고리즘의 필요성, 시간복잡도(Time Complexity)

 

그리고 이런 시간복잡도를 표기하는 방법 중, 가장 대표적으로 쓰이는 빅오 표기법이

우리에게 어떠한 것을 말해주고 싶은 것인지 설명하겠다.

 

 

 

# 빅오 표기법(Big-O Notation) 이 우리에게 말하고자 하는 것.

 

일단, 빅오 표기법의 가장 큰 특징은 '최악의 경우(Worst Case)' 를 대비하게 해준다.

 

좀 더 상세히 말하자면,

 

어떠한 특정문제를 해결하기 위해 알고리즘을 작성하고,

그 알고리즘을 통해 문제를 해결할 때, 그리고 문제를 해결하기 위한 데이터가 증가함에 따라 필요한

최소한의 연산 횟수를 알려준다고 보면 된다.

 

즉, 개발을 할 때 있어서 '성능을 가장 악화시킬 수 있는 상황' 만큼은 반드시 인지하며, 되도록이면 이러한 상황을 피해갈 수 있는 지표를 어느정도 제공해준다고 볼 수 있다.

 

 

우리의 일상 생활 속에서 일어날 수 있는 예를 잠깐 들어보자면 아래와 같다.

[ 인수 ], [ 원호 ], [ 민찬 ], [ 준범 ]은 오랜만에 만나서 여름의 마지막 강릉 여행을 가기위해 스케쥴을 짜고 있다. 즐거운 여행을 위해서는 쾌적한 숙박업체, 여행지로 가기위한 교통편, 그리고 이번 여행의 테마인 '먹고 죽자' 에 맞게 가서 양껏 먹을 수 있는 음식들과 주류, 음료들을 사야한다.

즐거운 여행을 위해서 야X자의 쾌적한 숙박업체를 알아보고, 최대한 빠르게 가기위해 서슴없이 KTX를 이용하기로 한다.그래서 숙박비와 교통비는 확실하게 1인당 정확하게 정해졌고, 이제 남은 식비만 정하면 될 것 같다.

하지만, 음식과 주류 같은 경우, 미리 사서 가기에는 짐이 될 것 같아 여행지 근처의 마트에서 사기로 하였다. 그래서 식비는 일단 인수가 생각한 선으로 해서 금액을 정하였고, 4명은 여행을 출발하였다. 

비록 여행 출발과 동시에 [ 원호 ] 는 배탈이 나면서 수시로 화장실을 들락날락거렸지만, 그래도 여행지에 도착하고나서는 조금 안정되어 즐겁게 저녁까지 시간을 보냈다. 그리고 저녁시간이 다되었고, 슬슬 마트로 장을 보러가야되는 상황이다. 배탈이 난 [ 원호 ]를 숙소에 잠시 쉬게하고 나머지 인원들끼리 마트로 장을 보러갔다. 그리고 [원호]가 배탈이 나서 많이 못먹을 것을 예상해서 4명 분이서 먹을 음식보다 조금 더 적게 샀다.

마트로 장을 보고, 숙소에 돌아와보니 배탈이 났던 [ 원호 ] 가 이제 괜찮아졌다며, 낮부터 아무것도 먹지못해서 몹시 배가 고프다고 한다. 일단 사온 음식을 먹어보자고 하였지만, 금새 바닥이 났다. 심지어 나중에 A) 술안주로 먹으려고 했던 소세지까지 [ 원호 ] 가 싹쓸이 한다.

[ 인수 ]와 [ 준범 ] 이 마트에서 다시 안주를 사오고 나서 숙소에 돌아와보니, 이번엔 갑자기 [ 민찬 ] 이가 빈 소주병을 들고 이러지리 뛰기 시작한다. 아마 그새 못참고 혼자 술을 왕창 먹다가 취한 것 같다. 결국엔 인수, 원호, 준범이 B) 마실 술이 부족해진 상황이다.  

하는 수 없이, 다시 [ 인수 ]는 마트로 갈려고 하는 데, [ 준범 ] 이 걱정스러운 표정으로 [ 인수 ] 에게 묻는다.  "형, 근데 돈 부족하지 않아......?". 하지만[ 인수 ] 는 웃으며 "괜찮아, 식비는 일부러 넉넉하게 챙겼다~"라고 말한다.

그렇다. [ 인수 ]는 평소에 조심성이 많아서 이렇게 안좋은 상황이 일어날 수 있음을 어느정도 예상은 했고, 그에 따라 예산을 조금 더 넉넉하게 잡아서 아무렇지 않게 웃으며 대답할 수 있었던 것이다.

 

 

나름 내가 이해한 대로 비유해서 설명하려고 했는데 너무 길어졌다.

 

아무튼, 위 예시에서 보면 2가지 예외적인 상황이 생겨났다. 

 

1. 배탈났던 [ 원호 ] 가 다시 부활해서 일어난 A) 술안주로 먹으려고 놔뒀던 소세지가 이미 다 없어졌고~ ,

2. 술을 한번 먹으면 취할때까지 혼자서 마시는 [ 민찬 ] 으로 인해 B) 마실 술이 부족해진 상황

 

그리고 다행히 이렇게 예외적인 상황까지 전부다 미리 생각해서 식비를 맞췄던 [ 인수 ] 덕분에, 위 여행의 테마인 '먹고 죽자'에 알맞은 여행이 가능했던 것이다.

 

결국 이러한 예시를 통해 말하고 싶었던 것은, 최악의 경우를 미리 인지할 수 있다면 그것에 대해 대비할 수 있게 되고, 대비까지 했다면, 목적 달성은 가능하다라는 것이다.  

 

 

즉, 개발 관점에서는 우리가 어떠한 문제 해결을 위해 특정 알고리즘을 짤 때,

가장 많은 수의 연산이 일어날 것이라는 것을 미리 인지할 수 있다면,

그것을 Dead 라인으로 보고 그 연산횟수보다 더 적게 나올 수 있는 알고리즘을 짜려고 할 것이다.

 

그래서 빅오 표기법(Big-O Notation)은 우리에게 이렇게 말한다.

 

"당신이 작성한 알고리즘은, 문제 해결을 위해 최소 N번의 연산을 하게된다."

 

그렇다고 해서 무작정 줄여라 하는 것은 아니고,

(* 숙박비나 교통비 같은 경우 열심히 찾아본다고 한들 최소한의 금액이 이미 정해졌기 때문에 더 줄인다고 하는 것에 의미가 없다. )

[ 줄일 수 있는 부분 ]은 확실하게 줄여서 '초기의 목적을 빠르게 달성하자' 라는 것을 제시해 준다.

 

 

 

* 백문이 불여일견, 바로 위의 " 줄일 수 있는 부분 ~ "  경우를 코드로 직접 보자.

그리고 어떻게 빅오표기법으로는 어떻게 표시되어지는도 같이 한번 보자

 

 

[ Test Data ]

위 주석에서 보이듯이, 2차원 배열 속에서 문자열 ( "a" )를 찾는 것이 목적인 알고리즘을 2개 작성해보겠다.

 

 

 

 [ Solution #1 ] 

Chrome 검사도구에서 실행된 결과 값.

 

위 solution #1은 두개의 forEach(배열 탐색) 메서드를 이용하여, 열과 행의 내부의 모든 요소를 검색해서 "a" 를 찾을 때까지 실행되는 함수이다.

그리고 목적 달성을 위한 알고리즘의 총 연산 횟수는 총 13회 이다.

 

 

 

 

 [ Solution #2 ] 

 

위 solution #2는 행에 대한 부분 행에 해당되는 부분만 검색해서, 그 행의 요소안에 "a" 가 있는지 확인( indexOf( ) )할 때까지 실행되는 함수이다.

목적달성을 위한 연산 횟수는 총 3회이다.

 

 

 

자 여기서,  

 

위의 solution #1 같은 경우, 열(N)과 행(N) 의 모든 요소를 탐색해야 하기 때문에, 최악의 경우 4 X 4 의 2차원 배열일 경우 최대 16번의 연산, 10 X 10 의 2차원 배열은 최대 100번의 탐색까지 필요할 수 있다.

 

즉, solution #1의 알고리즘 같은 경우, 데이터 크기가 증가함을 고려했을 때 목적달성을 위해 필요한 연산횟수는,

열과 행의 곱인 N의 2승(N의 2제곱) 일 것이다.

 

 

 

하지만, solution #2 같은 경우, 행(N)에 대해서만 연산을 1회씩 진행하기 때문에 4 X 4의 2차원 배열이라도 최대 4번의 연산, 10 X 10의 2차원 배열에서도 최대 10번의 연산만 하면 된다.

 

즉, solution #2 같은 경우에는 데이터크기가 증가함을 고려하더라도, 필요 연산횟수는 행의 숫자만큼만인 N에 그치게 된다. 

 

 

그리고 이러한 각 솔루션들을 빅오 표기법으로 표시할 경우,

solution #1 = O(N^2)

solution #2 = O(N) 

 

으로 표기되어진다.

 

 

 

[ 참고 ]

빅오(Big-O) 표기법에 의거한 성능의 지표는 위와 같다.

 

 

이번 글을 통해 빅오 표기법(Big-O Notation)이 우리에게 어떤 의미를 주는 지, 왜 신경을 써야하는 지에 대해서 알아보았다. 

 

그리고 위의  solution #1, #2 에서의 예를 들어서 표기법에 대해서 언급했지만,

빅오 표기법의 표시 기준에 대한 설명이 이번 장에서는 너무 부족한 것 같아 다음 장에 이어서 하도록 하겠다.