시간복잡도, Big O notation 정리

 

알고리즘을 공부하기 위해 가장 먼저 알아야 하는 것!

이해하기 쉽게 말하자면,

 

시간 복잡도 : 어떠한 문제를 해결하기 위한 데이터와 수행시간의 관계 (대충 느낌만 가집시다)

Big O : 시간 복잡도를 직관적으로 표현하는 방법

=> 데이터가 늘어날 때 알고리즘의 단계가 어떻게 바뀌는가? 

 

 

또 알아두어야 할 것이 있는데,

보통 알고리즘에서의 최악의 경우를 빅오로 나타낸다. -- 느낌만 가져가봅시다

선형탐색으로 예를 들자면,

1부터 100까지 있는 배열이 있고, 인덱스 0부터 하나씩 늘려가며 탐색을 하는 알고리즘을 가정했을 때

1을 탐색할 때는 O(1)이 되지만, 100을 탐색하고자 한다면? 

배열이 200까지 늘어나고, 200을 탐색하고자 한다면?

이는 O(N)이라고 표현하는 게 맞음

(O(N)이 무엇인지는 아래에 나옴)

 

출처: https://towardsdatascience.com/the-big-o-notation-d35d52f38134

 

데이터의 크기에 따른 단계를 보여주는 그래프이다.

빠른 순서대로 정리를 해보겠음

 

 

 

O(1)

 

가장 빠른 알고리즘 유형.

데이터의 크기와 상관없이 일정한 상수값을 갖는다.

데이터의 크기가 2배, 3배 혹은 그 이상으로 늘어난다고 해도

알고리즘의 단계에 영향을 주지 않는 경우 O(1)의 시간복잡도를 갖는다.

 

물론 데이터가 커지면 수행 시간은 당연히 조금은 늘어나지만, 데이터가 커진다고 해서 코드가 실행되는 단계가 늘어나는 것이 아니다.

이 때 주의해야 할 점은,

O(1)이 무조건 1단계의 과정을 거치는 것이 아니라는 거다.

가령, 데이터의 크기가 어떠하든 5단계의 과정을 거친다면 이또한 O(1)의 시간복잡도를 갖는 것이다.

 

ex) 배열을 단순히 읽는 경우

 

 

 

O(logN)

 

컴공에서의 O(logN)은 사실 O(log₂N)을 의미한다고 한다.

즉, O(logN)은 데이터가 1개가 될 때까지 데이터를 계속해서 반으로 줄여나가는 만큼의 단계가 걸린다는 의미이다.

만약 데이터의 크기가 두 배가 된다면 O(logN)을 갖는 알고리즘에서는 1단계가 추가되는 것임!

 

이진탐색(Binary Search), 퀵 정렬(Quick Sort), 분할 정복법(Divide and Conquer algorithm)이 대표적인 예임

얘네가 무조건 logN의 시간복잡도를 갖는게 아니라, 보통은 그렇다는 거임

****

분할 정복법은 DP와 비슷하지만 다름

(DP에서 sub-problem들의 솔루션으로 problem의 솔루션을 구할 수 있는 구조인데 분할정복법은 그냥 큰 문제를 작은 문제로 쪼개서 해결함 ㅇㅇ)

****

 

 

 

O(N)

 

데이터가 커지면, 그 정도에 비례하여 코드가 실행되는 단계가 많아진다.

선형탐색이 대표적인 예이다.

위에 적어둔 것처럼 데이터가 2배가 되면 수행하는 단계도 2배..라는 식임

 

 

O(N^k)

 

보통 loop을 중첩하는 경우 발생한다.

알고리즘 문제를 풀 때 자주 하는 짓...... 맨날 시간초과에 시달리는 이유..... ㅠㅠ

 

코드를 작성할 때 O(N^k)가 되는 경우는 최대한 피해야 한다.

즉, 꼭 필요한 경우가 아니라면 loop을 중첩해서 사용하는 것을 지양하는 것이 좋고

혹시라도 사용하게 될 경우, 성능 테스트는 필수적으로 하는 것이 좋다.

이런 시간복잡도가 나오도록 알고리즘을 짜게되는 경우... 시간이 많이 없거나 허접한 개발자(...)라고 여겨지곤 한다는데.....

물론 어쩔 수 없이 loop을 중첩해서 작성해야 하는 경우도 있지만

이런 경우, 왜 그렇게 작동해야 하는지, 큰 데이터를 다룰 경우 performance issue가 생길 수 있음을 문서화하라고 합니다..

 

ex)

어떤 알고리즘으로 1개의 데이터를 다룰 때 1ms, 2개의 데이터를 다룰 때 8ms, 3개의 데이터를 다룰 때 27ms의 시간이 걸린다면,

시간복잡도는 무엇일까?

-> O(N^3)을 갖는다. loop 중첩을 3개나 쓴 모양임..

 

 

끝