<TIL 20.06.23> Time Complexity( Big-O )

Time Complexity(시간 복잡도)

• 알고리즘의 효율성을 뜻한다.
• 알고리즘을 구성하는 명령어들이 몇 번이나 실행되었는지(연산의 실행 횟수)이다.

---

BIg-O표기법

• 알고리즘의 시간적인 측면과 공간(메모리)적인 측면으로써의 효율성을 나타낸다.

BIg-O표기법 특징

1. 상수항 무시하기 

  O(n+10)은 O(n)으로 표기한다.

 

2. 계수 무시하기  

  O(10n)은 O(n)으로 표기한다

 

3. 영향도 큰 부분만 나타내기

  O(n^2 + n)은 O(n^2)으로 표기한다

 

BIg-O표기법 종류

▶  O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘 (Constant Time)   

  

• 가장 빠른 시간 복잡도를 가진다.
• 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.
• 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

 

▶ O(n): 입력 데이터의 크기에 비례해서 처리시간에 걸리는 알고리즘 (Linear Time)

• 데이터양에 따라 시간이 정비례한다.
• Linear search, for 문을 통한 탐색을 생각하면 된다.

 

▶O(n^2): Quadratic

 

• 데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않아서 사용 거의 X)
• 해당 유형은 이중 Loop내에서 입력 자료를 처리 하는 경우에 나타난다.

 

▶ O(log n): Logarithmic

• 데이터양이 많아져도, 시간이 조금씩 늘어난다.
• 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 된다.
• 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
• 만약 입력 자료의 수에 따라 실행 시간이 이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. (주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형)

 

---

각 효율성 비교

[fast]     O(1) >  O(log n)  >  O(n)  >  O(nlog n)  >  O(n²)  >  O(2ⁿ)    [slow] 

 

 

 

 

 

 

이미지 출처 : https://velog.io/@760kry/Big-O , https://www.bigocheatsheet.com/