2. 빅오 표기법 - 시간복잡도

왜 공부하지?

지금껏 간단한  CRUD 웹앱을 만들어본게 다인 현재의 입장에서

아직 자료구조와 알고리즘이 실무에서 직접적으로 중요성으로 다가올 기회가 없기 때문에. 아직 큰 중요성을 솔직히 못느끼고있다.

그럼에도 불구하고 취업이라는 관문의 크기를 좁히고싶지않다면 개발자로써 맞서 부딪혀야하는 벽들을 넘기 위해서 

자료구조와 알고리즘은 중요하기때문에 공부해야한다.

 

교육자료는 학교교육사업을 통해 듣는 프로그래머스 온라인 교육과 

온라인교육플랫폼인 유데미에서 결제해서 듣는 자료구조알고리즘 강의 Colt Steele의 자료구조 알고리즘 강의를 참조

더나은 코드는 무엇일까?

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

var t1 = performance.now();
addUpTo(1000000000);
var t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)

function addUpTo(n) {
  return n * (n + 1) / 2;
}

var time1 = performance.now();
addUpTo(1000000000);
var time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)

3가지 시선으로 바라볼수 있다.

1. 가독성이좋은코드인가(코드가 짧은가)?

2. 메모리를 적게 사용하는가?

3. 빠른가?

 

셋다 중요하다! 하지만 일단은 속도를 중점으로 비교해보자

속도 비교 방법 performacne.now() OR  Date()

 

이러한 속도 측정을 통해 효율적인 코드를 판단하는것이 합리적인 방법으로 보이나

실제로 코드의 속도를 측정해보았을떄 매번 다르게 나오는 경우가 존재한다.

(첫번째 방법의 경우 계속 다른 속도로 차이남)

이러한 시간을 측정하여 더 좋은 코드를 판단하는 방법에는 세가지 문제가 존재한다.

1. 기기마다 다른 속도 측정

2. 같은 기기라도 속도를 완벽하게 측정하지못한다 (위에서 매 코드 실행때마다 다른속도가 나오는 문제확인)

3. 엄청 빠른 알고리즘이면 속도를 측정할수도없음(간혹 진짜 빠른알고리즘이 존재함)

 

즉 시간을 측정하는 함수를 통해 코드실행속도를 측정하는것은 미세한 차이에서의 문제가 존재한다.

그렇다면 연산의 갯수를 측정해보는것은 어떨까?

 

연산 갯수 측정하기

 

3번 연산하는것과 

5n + 2개만큼 연산하는것

(반복문안에서의 n개의갯수에 비례한 연산 1. i < n ,  2. i = n , 3. i++ , 4. total + i  ,  5. total = total + i)

(반복문밖에서의 상수개만큼의연산 1. total = 0, 2. i = 1)

 

여기서 중요한것은 연산하나하나의 갯수의 중요성보다도 결국 전체적인 큰그림

n개의갯수와 비례해서 연산의 횟수가 얼마인가?가 중요하다.

 

퍼포먼스 측정해보기 

Big O Introduction

이곳에서 시간복잡도를 시각화된표로확인가능하다.

 

n이 10000000일때 각각 어떤지를 확인해본결과

1번 파란색

2번 회색

 

1번쨰는 n의 크기에 비례해 1:1 로 연산횟수가 선형으로 증가함을알수있고

2번째는 연산횟수의 변화가 거의없음을 알수있다. 

 

 

Big o 빅오는 입력의 크기(n)와 실행시간의 관계를 말함 

 

n의 크기와 상관없이 일정하게 같은 연산횟수를 보인 1번째 방법의 경우 O(1)이라고하고

n의 크기와 비례하여 1:1로 선형으로 연산횟수가 증가함을 보인 2번째 방법을 O(n)이라고한다. 

 

 

반복문이 한번나올경우 O(n)이였는데 두번 그것도 중첩이되서 반복되는경우에는 어떨까?

이럴경우 n * n 즉 n의 제곱으로 O(n²)이되는것이다.

 

선형으로증가하지않고 n제곱의값으로 증가함을 알수있다.

 

 

빅오 표현식의 단순화 

 

n이아닌 연산과 숫자들은 의미가없다. n이 1000이라고 치고

3번째 O(N^2 + 5n + 8)에 대입해보면  1000^2 = 1000000   5n = 5000 + 8  다합치면 10만 5천 8인데 10만이나 사실 별차이가 없다라는것이다.

이 시간 복잡도 그래프를 보면 o(n)이 o(n^2)보다 훨씬 괜찮다라는 사실을 이제는 알 수 있게 될 것이다.