[Algorithm] 시간 복잡도

Las Vegas O Show 생각이 나서.. :)

개념 설명을 위한 글입니다.

 

[시간복잡도]

시간복잡도 그리고 공간복잡도, 알고리즘의 성능을 나타내는 두가지 지표이다.

시간복잡도가 시간을 정량화 하는 수단 중 하나라면, 공간복잡도는 작성한 알고리즘이 얼마만큼의 리소스(메모리)를 사용하는가를 측정하는 수단이라고 볼 수 있다.

 

본 글에서는 시간복잡도에 대해 간단히 정리해보려고 한다. 알고리즘을 많이 푸는 것도 좋지만 방법론과 개념을 베이스로 깔고 가는것도 중요하다고 생각하는 미래의 꼰대 새싹

 

Wiki

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다.
알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다.
이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적(Asymptotic)으로 묘사한다고 말한다.

예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다.

 

위의 위키에서 인용한 점근적 표기법은 아래 세가지가 있다.

• Best case: 오메가 표기법 (Big-Ω Notation)
• Average case : 세타 표기법 (Big-θ Notation)
• Worst case : 빅오 표기법 (Big-O Notation)

알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간인 빅오 표기법을 사용한다.

 

---

[빅오 표기법과 수행시간]

 

빅포 표기법 예시

• O(1): 상수(constant) 형태 -
  • 예시: 1회성 코드
    

    function test() {
      console.log("hello, Daniel!")
     }​

• O(n): 선형 형태
  • 예시: for loop

  • function test() { 
      for(let i=0; i<10; i++) {
        console.log("hello, Daniel!")
       }
     }

• O(log n), O(nlogn): 로그(Logrithmic) , 선형 로그 형태
  • Binary Search 또는  merge sort와 같은 알고리즘
• O(n^2): O(n^2), O(n^3) 와 같은 다차(polynomial) 형태
  • 예시: 다중 Loop

  • function test() { 
      for(let i=0; i<10; i++) {
          for(let j=0; j<10; i++) {
             console.log("hello, Daniel!")
          }
       }
     }

• O(2^n): O(2^n), O(3^n) 와 같은 지수(exponential) 형태
• O(n!): 5!와 같은 팩토리얼(factorial) 형태

 

시간의 증가에 따른 각 수행시간 표

시간 수행/ n	1	2	3	4	8	16	32	64	1000
1	1	1	1	1	1	1	1	1	1
log n	0	1	1.58	2	3	4	5	6	9.97
n	1	2	3	4	8	16	32	64	1000
n log n	0	2	4.75	8	24	64	160	384	9966
n^n	1	4	9	16	64	256	1024	4096	1000000
n^3	1	8	27	64	512	4096	32768	262144	1000000000
2^n	2	4	8	16	256	65536	4294967296	약 1844경	약 1.07 x 10^301
n!	1	2	6	24	40320	20922789888000	약 2.63 x 10^35	약 1.27 x 10^89	약 4.02 x 10^2567

 

위의 표는 각 수행시간 T(n)이 n이 증가함에 따라서 증가하는 cost를 잘 보여주는 예시이다

X축 n(element)에 따른 y축 operation(수행 수)

위의 그래프는 각 수행시간 T(n)이 n이 증가함에 따라서 증가하는 operation cost를 잘 도식화 되어있어 많이 인용된다.

---

[알고리즘, 자료구조, 그리고 시간 복잡도]

 

정렬 알고리즘에 따른 시간 복잡도 비교 표

Sorting Algorithm	최선	평균	최악
Bubble Sort	O(n)	O(n^2)	O(n^2)
Heap Sort	O(n log n)	O(n log n)	O(n log n)
Insertion Sort	O(n)	O(n^2)	O(n^2)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n^2)
Selection Sort	O(n^2)	O(n^2)	O(n^2)
Shell Sort	O(n)	O(n log n^2)	O(n log n^2)

위의 표는 각 정렬 알고리즘이 input에 따라 최선, 평균, 최악 경우에 따라 걸리는 시간을 Big O notation으로 표기한 것이다.

최악(Worst) Case만을 고려하면 Heap, Merge sort가 성능이 우수하다고 볼 수 있다.

 

 

자료구조에 따른 시간 복잡도&사용 패턴 케이스 비교 표

Data Structure	Average				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
Queue	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
Single Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
Double Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
Hash Table	N/A	O(1)	O(1)	O(1)	N/A	O(n)	O(n)	O(n)
Binary Search Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(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)	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)	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)	O(log n)	O(log n)

위의 표는 시간 복잡도 그리고 자료구조를 사용하는 패턴 케이스에 따라서 수행 시간을 빅오 표기법으로 나타낸 예시이다.

어떤 자료구조는 Access할때 최고의 성능을 보여주지만, 그렇지 않은 케이스도 있다.

 

요즘에는 하드웨어가 워낙 좋아서, 고려하지 않기도 하지만 알고있는 것도 좋을듯 하다.

---

[알고리즘 방법론과 시간 복잡도]

알고리즘 방법롭은 다 다루기에는 크다.

하지만, 알고리즘 방법론을 공부하는 이유 중 하나는 시간 복잡도를 고려하여 최대한 줄이는 목적도 있다고 생각한다.

 

같은 문제를 Brute Force로 풀면 O(n^2)로 풀거나 O(n^n)으로 풀 수도 있지만, Dynamic Programming 또는 Divide & Conquer를 사용해서 O(n log n) 또는 O(log n)으로 끌어내릴 수도 있다.

 

문제를 풀다가 Time out 이슈를 경험해보았을텐데, 코딩 테스트에서 이 부분이 꽤나 유의미한 결과를 보여준다. 

---

[Reference]

https://ko.wikipedia.org/wiki/시간_복잡도

https://namu.wiki/w/시간%20복잡도

https://www.bigocheatsheet.com