1. 시간복잡도

자료구조와 알고리즘(복습)!!!

코테와 개인 풀스택 개발 프로젝트, AWS Builders 기초 강의 수강 등을 해 보면서 전공자들에 비해 부족한 부분을 많이 느꼈다. 특히 알고리즘을 짤 때 머릿속에서 빙글빙글 맴도는 방법을 어떻게 코드에 녹여낼 수 있는지 고민하다가, 하루가 훌쩍 지나가버리거나, 웹 검색으로 쉽게 해결할 수 있는 간단한 함수로 해결하는 경험들(부끄러운ㅠㅠ)을 하면서, 알고리즘의 기초 지식에 대한 공부의 열망을 더욱 느꼈다.

 

React, Next.js 등의 현업에서 쓰이는 라이브러리 공부와 함께, 알고리즘 독학을 진행하면서 모자라고 부족한 부분을 더욱 더 채워넣고자 한다.

시간 복잡도란 코드를 진행시키는 데 (데이터를 순회하는 데) 시간이 얼마나 걸렸는가를 의미

* 공간 복잡도: 메모리를 얼마나 차지하는가(최근에는 하드웨어가 많이 발전하여 크게 의미가 없음)

 

빅 노테이션

빅오, 빅세타, 빅오메가(자료구조와 알고리즘의 성능을 표시하기 위함), 유명한 것은 빅오

 

[1, 2, 3, 4, 5]라는 배열이 있을 때 

'3'이라는 특정 값을 찾을 때는 바로 그 값에 접근하면 되지만(1),

가장 오래 걸리는 작업량은 (1, 2, 3, 4, ...5)로 배열 전체의 값을 전부 순회하는 것이다.(실제로는 이런 방식의 처음부터 하나하나 끝까지...등의 알고리즘은 빅 노테이션으로 치지도 않는다. '바보 알고리즘')

데이터의 총 갯수를 N이라고 하면, 어떤 배열에서 어떤 값을 찾는 작업량은 N이라고 표시할 수 있는 것이다.

 

빅 오 - "최악의 경우" 

• 가장 많이 활용하는 경우, Big O Notation(빅오 표기법)이라고 함
• 자료구조나 알고리즘이 얼마나 효과적인지를 판단하기 위해 사용함
• O(1), O(logN) ,O(N), O(NlogN) O(N*N), O(N*N*N), O(2n(승)), O(N!) 등이 있는데, 괄호 안의 값이 점점 커질 수록 비효율적이고 오래 걸리는 알고리즘
• 실무에서는 O(N*N)까지가 마지노선
• 최악의 경우라고 해서 배열 전체의 값을 순회하는 것이 아니다! 빅오 노테이션은 최선을 다했는데도 최악이 나오는 경우를 의미함

[1, 2, 3, ..., 100] 까지의 배열 안에서 특정 값 N(1<= N <= 100)이 있다고 하자.

N을 찾을 때 1부터 100까지의 배열을 전부 순회하는 것을 O(N)이라고 함, 이것은 바보 알고리즘으로, 이런 방식을 사용하지 않는다

예를 들어 N = 47일 때, 

1. N = 50? Down

2. N = 25? Up

3. N = 37? Up 

4. N = 44? Up

이런 식으로 반씩 좁혀가는 알고리즘이 훨씬 효율적이다. 이런 방식을 O(NlogN)이라 표현한다.

 

가장 빠른 경우 - O(1)은 상수라고 부른다.

 

그렇다면 내 실제 코드에서 N을 어떻게 판단할 수 있는가?

가장 쉽게 보는 방법은 javascript로 치면 for문이다.

O(N):  for(let i = 0, i < arr.length, i++) { ... } 

O(N*N): for(let i = 0, i<arr.length, i++) {

                   for(let j = 0, j<arr.length, j++){ ... }

              }

O(NlogN):

for(let i = 0, i<arr.length, i++) {

                   for(let j = 0, j<arr.length, j*2){ ... }

              }

실제는 수백만, 수천만개의 천문학적인 갯수의 N이 있다. 이러한 경우 O(N*N(제곱))의 경우에는 그 숫자가 조, 경 단위가 되므로 절대 피해야겠지만, O(2N)의 경우는 기존 N과 비교하여 크게 달라지지 않는 것이다. 따라서 O(N)과 O(2N)은 같은 것으로 친다.

* O(NlogN)과 O(N*N) 중 무조건 O(NlogN)이 좋은가?

- N이 충분히 크지 않은 경우, 오히려 O(N*N)이 더 좋을 수도 있다!

 

빅 세타 - "최악 = 최선일 경우"

 

빅 오메가 - "최선의 경우"

• 대부분 최선의 경우는 별로 의미가 없음

 

실전에서 쓰이는 경우:

실제 서비스 운영 과정에서 삽입, 조회, 수정, 삭제 등이 일어난다. 이 때 삽입에 적합한 자료구조, 조회에 적합한 자료구조 등 각각의 경우에 따라 적합한 자료구조와 알고리즘이 있다. 이런 부분들을 적절히 조합하면 효과적으로 서비스를 운용할 수 있을 것이다.