[스타트 위드 유데미] - 빅오(Big O) 표기법의 필요성

* 이 포스팅은 Start with Udemy 챌린저로써 강의를 수강하며 작성하는 내용입니다.😊 *

 

 

Section 2를 시작하면서

드디어 소개 챕터 다음인 빅오 표기법 파트를 들어보았다.
이번 챕터는 총 1시간 2분짜리였는데 유데미의 강의는 5분, 10분 정도의 길이로 나누어져 있어서 집중력이 좋지 않아도 듣기가 편했다.

이 챕터가 자바스크립트 알고리즘 & 자료구조 마스터 클래스의 수업을 듣는 것에 있어서 매우 중요한 시작 역할을 한다고 하여 집중해서 들어보았다.

이번 파트에서는 빅오의 정의, 시간 복잡도, 공간 복잡도 개념에 대해서 배우게 된다.
오늘 포스팅은 빅 오의 정확한 표기방법에 대해 알아보기 전에 코드 성능 비교가 왜 필요한지에 대해서 포스팅 해볼것이다. 차근차근 시작해보자.

 

 

빅오(Big O)가 필요한 이유 알아보기

시작부터 Warning이라는 글자가 나와서 당황했지만, 놀라게 하려는 것이 아니라 격려를 해주기 위함이라고 하시는 강사님ㅋㅋ 은근히 유머감각이 있으신 편인 것 같다.

 

1. 알고리즘 평가하는 방법 생각해보기

빅오가 무엇인지 알려면 먼저 알고리즘을 평가하는 방법에 대해서 생각해보아야 한다.

어떤 알고리즘 문제가 있으면, 모든 사람이 같은 방법으로 문제를 해결하지는 않는다.
각자 다양한 방법을 사용하여서 문제를 해결할 수 있다. 그런데 어떤 방법이 가장 좋은 방법인지 알아내려면 어떻게 해야 할까?🤔

예를 들어 아래와 같은 문제가 있다고 가정해보자.

"문자열을 받아서 이것을 뒤집어 출력하는 function을 쓰세요"

머릿속에 여러가지 해결책들이 떠오를 것이다.
그리고 stack overflow에 검색을 해보아도 아래와 같은 수많은 결과들이 나온다.

제일 좋은 방법을 알아내려면 어떻게 해야 할까❓
하나하나 실행해보기? 짧은 코드 고르기? 
이 경우에는 간단한 예제이므로 그렇게 해볼 수도 있겠지만, 만약 매우 복잡한 코드일 경우에는 어떻게 해야 할까?
이럴 때를 대비해서 코드를 분류할 수 있는 시스템이 있다면 얼마나 좋을까?😢

바로 이런 점을 해결해주기 위해서 빅오가 나오게 되었다!

 

2. 빅오(Big O)란?

다음 강의가 되어야 정확한 개념과 사용방법을 알게 되겠지만,
지금 간략히 설명하면 "여러 가지이다.

이렇게 색과 감정으로 표시하는 것은 아니지만, 적어도 어떤 것이 좋은 코드인지, 어떤 코드가 엉망인 코드인지 Big O를 사용하면 구분할 수 있다.😆

그런데 이런 생각이 들 수도 있다. 코드가 돌아가기만 하면 되지... 성능까지 따질 필요가 있나?

어떻게든 돌아가기는하는 코드

어떤 간단한 코드에서는 이런 생각이 틀리지 않을 수도 있다.
하지만 복잡한 코드를 사용하여 문제를 해결하거나, 회사에서 어떤 문제를 해결해야 하는 상황이 있다고 생각해보자.

방법이 2가지가 있는 상황에서 1번 방법이 2번 방법보다 1시간이 빠르다면?
비즈니스에서 시간은 곧 돈이다.😱
문제 하나에 1시간이라면 여러 문제가 합쳐진다면 엄청난 시간 차이가 발생할 것이고, 곧 비용과 직결되며, 이는 프로그램의 성능과도 직결된다.
이처럼 코드의 성능을 따져보는 일은 매우 중요하다. 그런데 어떻게 하면 코드의 성능을 따져볼 수 있을까?🤔

 

3. 코드 시간 재보기

위의 두 가지 예시를 소요 시간을 측정하여 코드 성능을 비교해보자. 소요시간 비교에는 performance.now( )  함수를 사용한다. 코드 시작 전과 후의 차이를 이용하여 시간을 구한다.

1.25초와 0.00010초가 나온다. 즉 시간 소요가 짧은 코드가 좋은 코드라면 오른쪽의 경우가 더 좋은 코드라고 할 수 있다.
하지만, 매번 코드마다 performance.now( )를 써서 시간을 구해보는 것은 너무 비효율적이다. 그리고 시간으로 비교 시에는 아래와 같은 문제점이 있다.

• 기기마다 다른 방식으로 시간을 기록하여 오차 발생 가능성이 존재한다.
• 같은 기기라도 사용방법에 따라 다른 시간을 측정할 수 있어 오차가 발생한다.
• 매우 빠른 알고리즘의 경우, 너무 짧은 시간이 측정되어 정확도가 떨어질 수 있다.

따라서 시간 비교만으로는 충분한 코드 성능 비교방법이라고 볼 수 없다.

 

4. 연산의 개수 세어보기

앞에서 봤듯이 시간 만으로 코드 성능을 비교하기에는 어려움이 많다. 그럼 다른 방법은 어떤 것이 있을까?
바로 아래와 같이 연산의 개수를 비교해 보는 방법이 있다.

위의 예시는 곱셈, 덧셈, 나눗셈 총 3번의 연산을 한다.

for문이 있는 위의 예시의 경우, for 루프 안의 연산과 루프 밖의 연산으로 나누어서 생각할 수 있다.
만약 n이 5라면 5번, 10이라면 10번 이렇게 for loop안의 연산은 n의 값에 따라서 변한다.
즉, n번의 연산을 한다고 생각해야 옳다. 위의 예시는 총 5n + 2번의 연산을 한다.

코드 성능을 비교할 때 매번 이렇게 측정해야 하는 것은 아니다. 중요한 것은 큰 그림으로 생각해야 한다는 점이다.
3번과 5n + 2를 비교하면 n이 커질수록 5n + 2의 값이 커지고, 아무리 숫자가 바뀌어도 3번의 연산이 더 작으므로 이 방법이 더 좋은 코드라고 볼 수 있다.
하지만 5n + 2든, 3n이든, 50n 이든 중요한 것은 연산에 n번이 들어간다는 점이다. n이 커질수록 연산의 개수도 비례적으로 늘어난다.

 

결론

• Big O란 코드의 성능을 비교하기 위해서 나오게 된 개념이다.
• 코드 소요 시간으로만 비교하면 컴퓨터에 따라 다른 값이 나오거나, 같은 기기라도 다른 결과값이 나올 수 있는 등의 문제가 있어서 적합하지 않다.
• 연산의 개수로 비교하는 방법은 하나하나 따지기보다 큰 그림으로 보아야 한다.
• 즉 2가지 방법을 합친 방법이 필요하다. (👉🏻 Big O)

다음 포스팅부터 본격적으로 Big O의 사용방법과 시간 복잡도, 공간 복잡도를 구하는 방법에 대해 정리해볼 것이다.