알고리즘 시간 복잡도(Time Complexity) 쉽게 이해하기

알고리즘과 시간 복잡도는 컴퓨터공학을 배우는 이들에게는 매우 익숙한 용어입니다. 학교에서 배우는 많은 이론들 중에 하나이지만 막상 한번 들어서 이해가 안되는 상황들이 발생합니다. 왜그럴까요? 아마도 이것이 나의 삶과 어떻게 연결이 되고 있는지 실감이 나지 않기 때문일 것입니다.

그러나 오늘 이글을 소개하는 것은 이러한 개념이 향후 알고리즘을 다루는 개발자로 성장할 때에 매우 중요한 기본개념이기 때문에 상식적으로 꼭 알아두기를 바랍니다. 시간 복잡도를 이해하기 위해서는 먼저 알고리즘이 무엇인지 생각해 보아야 합니다.

 

 

알고리즘이 뭔가요?

알고리즘은 결과물을 만들어 내기 위해 거쳐야 하는 일련의 과정들을 의미합니다. 이러한 표현은 영어로 알아두면 더 도움이 됩니다.

Algorithm is a series of contained steps which you follow in order to achieve some goal, or to produce some output

구체적인 예를 들어볼까요? 알고리즘과 시간 복잡도를 영어로 쉽게 설명한 아래 글을 참고하시기 바랍니다.

https://www.freecodecamp.org/news/time-is-complex-but-priceless-f0abd015063c/#.j7h5s1m2p

Algorithms in plain English: time complexity and Big-O notation

원문에서 소개된 할머니까 빵을 굽는 알고리즘입니다. 

function BakeCake(flavor, icing){
"
 1. Heat Oven to 350 F
 2. Mix flour, baking powder, salt
 3. Beat butter and sugar until fluffy
 4. Add eggs.
 5. Mix in flour, baking powder, salt
 6. Add milk and " + flavor + "
 7. Mix further
 8. Put in pan
 9. Bake for 30 minutes
10." + if(icing === true) return 'add icing' + "
10. Stuff your face
"
}

BakeCake('vanilla', true) => deliciousness

쉽게 이해가 되시나요? function 이나 제일 하단의 function 을 실행하는 부분에 대한 부분은 제외하고 1- 10 까지의 과정을 주의깊게 보시기 바랍니다. 요리를 위해 진행되는 순서이죠. 이것을 알고리즘이라고 표현합니다. 이런 알고리즘은 일상적인 언어로도 만들어지지만 개발자들은 각자가 사용하는 Python, Java 와 같은 언어들로 표현합니다. 우리는 이것을 알고리즘이라 부릅니다.

 

시간 복잡도(Time Complexity)는 뭔가요?

실행시간이라는 관점에서 알고리즘의 효율을 측정하는 표기법을 말합니다. 일반적으로 다음과 같은 표기법의 종류가 있습니다.

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

 

개발자들의 실무영역에서는 일반적으로 최악의 경우를 고려한 빅오 표기법을 사용합니다.

Big-O 표기법은 알고리즘의 전체 단계를 대수 용어로 변환 한 다음 문제의 전체 복잡성에 큰 영향을 미치지 않는 하위 상수 및 계수를 제외하는 방법입니다. 수학자들은 아마도 "전체적인 영향" 을 고려한 공식을 선호할 수있지만 개발자들에게는 시간을 절약하기 위해 방식을 단순화하여 사용합니다. 

개념을 정의 했지만 여전히 다가오지 않는 것 같습니다. 일단 중요한 포인트는 복잡도를 간소화하여 나타내는 표기법 이라는 것입니다. 다음 예제를 봅시다.

Regular       Big-O

2             O(1)   --> It's just a constant number

2n + 10       O(n)   --> n has the largest effect

5n^2          O(n^2) --> n^2 has the largest effect

반복문이 아닌 단순한 문장이나 실행문은 O(1) 으로 표기됩니다. 

루프문의 시작에서 n 까지의 반복은 O(n) 으로 2n + 10 과 같은 식으로 알고리즘이 분석되어도 O(n) 입니다.

루프문이 2개의 중첩을 가지고 있다면 O(n^2) 으로 됩니다. 5n^2 과 같이 알고리즘이 나오면 O(n^2) 입니다. 

가능하면 다음과 같이 영어로 빅오 표기법에 익숙해지기를 바랍니다. 

• O(1) — Constant Time: Given an input of size n, it only takes a single step for the algorithm to accomplish the task.
• O(log n) — Logarithmic time: given an input of size n, the number of steps it takes to accomplish the task are decreased by some factor with each step.
• O(n) — Linear Time: Given an input of size n, the number of steps required is directly related (1 to 1)
• O(n²) — Quadratic Time: Given an input of size n, the number of steps it takes to accomplish a task is square of n.
• O(C^n) — Exponential Time: Given an input of size n, the number of steps it takes to accomplish a task is a constant to the n power (pretty large number).

 

영어로 알아두면 좋은 점은 Facebook 과 같은 글로벌 기업에서 코딩 테스트를 볼 때에 시간복잡도에 대한 부분을 반드시 질문하고 이것을 영어로 표현하는 부분이 필요합니다. 특히, 코딩 테스트의 경우는 Codepad(https://coderpad.io/) 와 같은 온라인 코딩 공유 환경에서 코딩을 영어로 설명하며 테스트를 치루어야 합니다. 평소에 시간복잡도와 영어로 표현하는데 익숙해지면 도움이 될 날이 올것이다.

일반적으로 수학에서는 제곱은 x squared, 3제곱은 x cubed, X⁴부터는 'X to the fourth' 와 같이 표현된다.

 

원문의 예제를 더 살펴봅시다. 

let n = 16;

O (1) = 1 step "(awesome!)"

O (log n) = 4 steps  "(awesome!)" -- assumed base 2

O (n) = 16 steps "(pretty good!)"

O(n^2) = 256 steps "(uhh..we can work with this?)"

O(2^n) = 65,536 steps "(...)"

이해가 되시나요? Log n 의 케이스는 루프가 Log 단위로 줄어들었을 때를 말합니다.

 

Linear Time 과  Quadratic Time, Exponential Time 도 알고리즘의 복잡도(일반적으로 루프)에 따라서 단계의 증가를 보게 됩니다. 아래 그래프를 통해 더 쉽게 생각해보기 바랍니다. 

 

각 항목의 자세한 예제는 위의 링크된 원문을 통해 확인해 보기 바랍니다.

a=8 # Constant 1
b=9 # Constant 1
c=40 # Constant 1

for i in range(n):
    for j in range(n):
        x = i * i # n^2 
        y = j * j # n^2
        z = i * j # n^2
        
for k in range(n):
    w = a*k + 108 # n
    v = b*b # n
    
d = 55 # Constant 1

위의 예제를 정리해 보면 T(n) = 3 + 3n^2 + 2n + 1 = 3n^2 + 2n + 4 로 정리가 되며 O(n^2) 으로 표기된다.

이러한 시간 복잡도는 데이터 구조와 알고리즘에 따라서 구분이 되기도 합니다.

 

시간복잡도를 구하는 요령

각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
• 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)

 

정렬 알고리즘 비교

Sorting Algorithms	공간 복잡도 최악	공간 복잡도 최선	시간 복잡도 평균	시간 복잡도 최악
Bubble Sort	O(1)	O(n)	O(n2)	O(n2)
Heapsort	O(1)	O(n log n)	O(n log n)	O(n log n)
Insertion Sort	O(1)	O(n)	O(n2)	O(n2)
Mergesort	O(n)	O(n log n)	O(n log n)	O(n log n)
Quicksort	O(log n)	O(n log n)	O(n log n)	O(n log n)
Selection Sort	O(1)	O(n2)	O(n2)	O(n2)
Shell Sort	O(1)	O(n)	O(n log n2)	O(n log n2)
Smooth Sort	O(1)	O(n)	O(n log n)	O(n log n)

일반적으로 Quicksort, merge sort, binary search, depth-first search, breadth-first search 와 같은 정렬과 검색에 대해서 잘 이해하고 있으면 좋습니다. 

 

자료구조 비교

Data Structures	Average Case Insert	Average Case Delete	Average Case Search	Worst Case  Insert	Worst Case Delete	Worst Case Search
Array	O(n)	N/A	N/A	O(n)	N/A	N/A
Sorted Array	O(log n)	O(n)	O(n)	O(log n)	O(n)	O(n)
Linked List	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Doubly Linked List	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Stack	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Hash table	O(1)	O(1)	O(1)	O(n)	O(n)	O(n)
Binary Search Tree	O(log n)	O(log n)	O(log n)	O(n)	O(n)	O(n)
B-Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
Red-Black tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
AVL Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)

일반적으로 Hash maps, linked lists, stacks, queues, trees, heaps, tries, graphs 에 대한 자료구조는 기본적으로 잘 다루는 것이 필요합니다. 

 

시간 복잡도에 대해서 참고할만한 링크를 공유합니다.

https://www.freecodecamp.org/news/time-complexity-of-algorithms/

An Introduction to the Time Complexity of Algorithms