빅 오 표기법 - O(1), O(N), O(log N)

이번엔,ㄴ... 안 보고 싶어도 항상 만나게 되는.. 빅 오 표기법을 이해해보겠습니다... 어짜피 자료구조 재수강해야되니까.. 일석이조다 이런 마음으로 하겠어요 하하하하하

 

"데이터 원소가 N개일 때 특정 알고리즘에 몇 단계가 필요할까?"

라는 질문에 대한 답을 우리는 빅 오 표현을 통해 내릴 수 있는데요. 빅 오 표현은  "O(N)" <- 이런 식으로 괄호 안에 몇 단계가 필요한지를 적어서 표기하곤 합니다.

 

*O(N)의 의미는?

: 데이터 원소의 개수가 N개일 때, 알고리즘에 N단계가 필요하다는 의미겠죠. 이 말 어디서 많이 보지 않았나요? 

.. 바로 전 글에서, 선형 탐색 알고리즘을 공부할 때 배웠습니다! 그래서 이것을 선형 시간을 갖는 알고리즘이라고 부르기도 합니다.

 

*O(1)의 의미는?

: 컴퓨터가 배열의 값을 '읽기' 하는 경우를 생각해봅시다. 배열의 읽기에 필요한 단계 수는 배열의 크기와 상관 없이 딱 하나입니다. 이처럼, N이 얼마든 항상 상수 단계만을 필요로 하는 알고리즘을 말하는데요. 그래서 이것을 상수 시간을 갖는 알고리즘이라고 표현하고 가장 빠른 알고리즘 유형으로 분류할 수 있습니다.

 

---

빅 오의 본질

:: 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는가

 

예시를 하나 들어보겠습니다. 데이터가 몇 개든 항상 3단계가 걸리는 알고리즘이 있다고 생각해봅시다. 이를 빅 오로 표현하면 어떻게 표현할 수 있을까요? 

=> O(3)일까요? 땡!!!!!!!!!!!!!!!!!!!!!!!!

=> 정답은 O(1)입니다. 

이유는, 빅 오의 본질은 '데이터의 수가 늘어나는' 상황에 있기 때문입니다. 데이터의 증가할 때 단계의 수가 어떻게 증가하느냐에 focus를 맞춰야 합니다. 따라서, 앞선 예제처럼 데이터 증가에 영향을 받지 않는,, 알고리즘은 O(1)과 본질적으로 같은 알고리즘이라고 볼 수 있겠습니다.

 

한편, O(N)은 그 유형이 다릅니다. 데이터의 증가가 성능에 영향을 미치기 때문입니다.

좀 더 명확하게 말하면, 데이터가 늘어날 때, 정확히 그 데이터에 비례해 단계 수가 증가하는 알고리즘 유형입니다.

그래프를 보면 O(N)은 완벽한 대각선(비례 관계)를 그리지만, O(1)은 완벽한 수평선을 그린다는 것을 알 수 있습니다.

 

---

자 여기서 한 가지 생각해 볼 부분이 있습니다.

선형 탐색 알고리즘을 한 번 떠올려볼까요! 만약 우리가 찾으려는 값이 배열의 첫번째 인덱스에 들어있다면 1단계만에 항목을 찾은 것이라고 할 수 있습니다. 이러한 사례를 빅 오 표기법으로 나타내면 O(1)이라고 할 수 있겠죠. 그러니까 전체적인 관점에서 선형 탐색 알고리즘의 효율성을 따져본다면, 최선의 시나리오에서 O(1), 최악의 시나리오에서 O(N)이라고 할 수 있습니다.

하지만 보통의 빅 오 표기법(표시가 없는 경우)은 일반적으로 최악의 시나리오를 의미한다는 것을 알고 있어야 합니다.

---

자 그렇다면, 우리가 전에 배웠던 이진 탐색 알고리즘(Binary search)를 빅 오 표기법으로 나타내면 어떻게 나타낼 수 있을까요? 정답부터 말하자면 O(log N)(첨자 2는 생략)으로 설명할 수 있습니다. 이진 탐색의 경우 데이터의 수가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘이기 때문입니다.

로가리즘을 접목해서 이를 설명해보자면, 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻인데.. 이건 그냥 쓱 이해만 하고 넘어가도 될 것 같습니다. 

어쨌든 O(log N)은 위의 그래프에서 볼 수 있듯,  O(1)보다는 덜 효율적이지만 O(N)보다는 훨 효율적이라고 할 수 있겠죠! 

 

 

포스팅을 마치기 전, 예제를 딱 하나만 풀어보겠습니다. 

예제: 체스판 한 칸에 쌀 한 톨을 놓는 상상을 해보자. 두 번째 칸에는 이전 칸에 놓았던 쌀 양보다 두 배 더 많은 쌀 두 톨을 놓는다. 세 번째 칸에는 쌀 네 톨을 놓는다. 네 번째 칸에는 쌀 여덟 톨을 놓고 다섯 번째 칸에는 쌀 열여섯 톨을 놓는 식으로 이 과정을 반복한다. 함수는 몇 번째 칸에 일정한 수의 쌀을 놓아야 하는지 계산한다. 가령 쌀이 열여섯 톨이면 다섯번째 칸에 놓아야 하니 함수는 5를 반환한다. 다음과 같이 구현한 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

function chessboardSpace(numberOfGrains) {
	let chessboardSpaces = 1;
    let placedGrains = 1;
    
    while (placedGrains < numberOfGrains) {
    	placeGrains *= 2;
        chessboardSpaces += 1;
    }    
    
    return chessboardSpaces;
    
}

--> 칸   1   |   2   |   3   |   4   |   5

            1       2       4       8      16   

=> 칸이 1 증가할 때마다 칸에 놓이는 쌀의 수가 2배 증가하는 것을 확인할 수 있습니다. 이는 이진탐색 알고리즘과 동일한 패턴을 가진다는 것..이 느껴지시나요? 그래서 정답은 O (log N)이랍니다. 뚜뚜뚱

 

 

다음 시간에는 버블정렬에 대해서 배워보겠습니다!_!_ 빠잉