section2. Big O notation

4. big o 소개

 

1. big o 표기법의 필요성
2. big o 표기법이란
3. big o 표기법의 표현법
4. 시간 복잡도와 공갑 복잡도의 정의
5. big o 표기법을 통해 알고리즘의 시간 복잡도와 공간 복잡도 표현하기
6. 로그란 무엇인가

 

-big o 표기법이란

big o 표기법이란 여러 코드를 서로 비교하고 각각의 성능을 평가하는 방법이다.

big o 표기법을 이용하면 코드의 성능을 숫자로 표기할 수 있고 그것을 통해 코드를 쉽게 분류할 수 있다.

 

-big o 표기법을 사용하는 이유(상세)

우리는 프로그램을 만들때 그 프로그램에 가장 최적화된 코드를 사용해야한다. 그렇기 때문에 코드를 분류하고 그 중에서 가장 좋은 코드를 찾아야 한다. 그래서 프로그래머는 자신이 만든 해결책이 만족스럽더라도 다른 해결책과 성능을 비교해보아야 한다. 이것을 가시적으로 보여주는 것이 big o 표기법이다.

 

big o표기법을 사용하면 우리는 정확한 용어를 이용해 코드의 성능을 이야기할 수 있다.

또한 단순히 하나의 기준을 가지고 문제의 접근법을 평가하는 것이 아니라 그 접근법이 가지고 있는 여러가지 장단점을 설명할 수 있도록 여러 기준을 가지고 있다. 예를 들어 시간복잡도와 공간복잡도 같은 것이 있다.

 

-이 강의에서 big o 표기법이 중요한 이유

이 강의는 알고리즘, 문제해결, 컴퓨터 공학과 데이터 구조에 대한 강의이다.

이 강의에 나오는 문제마다 수많은 해결법이 존재한다.

그중에 어떤것이 최고인지 평가하기 위해서 big o 표기법이 쓰인다.

 

 

 

5. 코드 시간 재기

더 좋은 코드는 무엇일까의 기준은 개발자마다 다르지만 대부분 비슷한 의견을 가지고 있다.

1. 좀 더 빠른 코드

2. 메모리를 적게 사용하는 코드

3. 가독성이 좋은 코드

4. 짧은 코드

그 중에서 1.속도와 2. 메모리 사용량이 가장 기본이 된다.

 

코드 간의 속도를 비교하기 위해서 사용되는 방법 중에 하나로 대입이 있다. 각각의 코드에 10억 정도의 값을 대입해서 실행시간을 구하고 그 값을 비교한다.

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

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

//실행시간을 구하기 위한 코드

let t1 = performance.now(); //performance.now()는 현재 브라우저를 켜놓은 시간
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)

문제는 이렇게 구한 실행시간이 컴퓨터마다, 시점에 따라 달라진다는 것이다. 또한 이 방법은 코드의 실행시간이 커질 수록 비효율적이다. 코드 하나를 실행하는데 한 시간이 넘게 걸린다면 결과가 나올 때까지 걸리는 시간은 그 이상이 될 것이기 때문이다.

그렇기 때문에 코드의 빠르기를 비교하기 위해서 우리는 변하지 않고 좀 더 정확한 방법을 찾아야 했다.

 

6. 연산 개수 세기

그래서 나온 것이 연산 개수를 세는 방법이다. 어떤 컴퓨터를 사용하든 연산 개수는 변하지 않기 때문에 이 방법을 사용하면 변하진 않는 값을 얻을 수 있다. 

 

연산 개수 세기 예제

연산 개수는 실제 연산자가 쓰인 개수를 통해 구할 수 있다. 반복문의 경우 그 반복문이 돌아간 횟수만큼이 곱해지는데 이러한 특성 때문에 반복문이 포함된 코드의 연산 개수는 n의 값에 따라 변화한다.

위의 첫번째 예제는 상수배, 두번째 예제는 n배의 연산 개수값이 부여된다.

 

하지만 사실 정확한 숫자는 상관 없다. 5n + 2이든지, 3n든지 50n 이든지 실상 어느 코드가 더 나은 코드인지는 대략적인 값만으로 비교할 수 있기 때문에 전체적인 추세만 구해도 상관이 없다.

Big O 표기법에서도 그렇다. 

 

7. 시간 복잡도 시각화하기

 

https://rithmschool.github.io/function-timer-demo/

Big O Introduction

 

 8. 빅오에 대한 공식소개

시간복잡도를 나타내는 Big O 표기법 정의는 "입력된 내용이 늘어날수록 알고리즘의 실행시간이 어떻게 변하는지 설명하는 공식적인 방식"이다. 이 표기법은 어떤 함수의 입력값이 늘어나는 것에 따라 함수 실행시간 변하는 관계를 표현한다.

 

시간복잡도 표기

 

O(1)

N의 값이 늘어났지만, 실행 되는 시간에 아무 영향을 받지 않았다.

 

O(N)

실행 되는 시간이 N의 값이 늘어나는것과 비례하게 거의 1:1 비율로, 선형으로 늘어났다. 똑같이 n이 커질수록  여기 있는 연산들이 n의 값만큼 늘어날 것이다.

 

 

9. 빅오 표현식의 단순화하기

이제부터 세세한 것을 따지지 않고 간단히 빅오 표기법을 사용할 수 있는 방법을 알려주겠다.

첫째, Big O표현법에는 O(1), O(n), O(n^2)... 같은 형태밖에 없다.

둘째, 상수, 변수, 배열의 요소, 객체 등은 O(1)로 표기하고, 반복문은 반복 횟수에 따라 O(n), O(n^2) 등으로 표기한다.

Math.max(n,5)처럼 1에서부터 5까지의 값은 5, 나머지는 전부 n에 비례하는 경우는 O(n).

Math.min(n,5)처럼 1에서부터 5까지의 값은 n, 나머지는 전부 5인 경우는 O(1)로

전체적인 추세를 대표하는 값을 따라간다.

 

위부터 각각 O(n), O(1), O(n), O(n)

10. 공간 복잡도

앞서 좋은 코드를 나누는 기준은 속도와 메모리 사용량이라고 했다. 이번에는 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지 하는지에 대해서 얘기해보겠다. 여기서 말하는 공간 복잡도는 보조 공간 복잡도를 말한다. 그것은 입력 되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간을 의미한다.

 

공간 복잡도는 단순히 말하면 배열이 있으면 O(n) 없으면 O(1)이다.

이것은 배열이 초기화되기 전에는 n이 무한대로 향하며 n이 커질수록 입력이 커지기 때문이다.

 

위부터 각각 O(1), O(1), O(1), O(n), O(n)

https://pstudio411.tistory.com/entry/Big-O%EC%99%80-%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity

알고리즘의 기초 Big-O Notation과 복잡도(Complexity)

 

그래프를 표기할 때의 complexity

https://codermun-log.tistory.com/288

그래프_시간복잡도와 공간복잡도(인접 행렬, 인접리스트)