시간복잡도(Time Complexity)

1. 시간복잡도(Time Complexity)란?

[시간복잡도]

시간복잡도 / 출처 :https://towardsdatascience.com/introduction-to-big-o-notation-820d2e25d3fd

시간복잡도는 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것입니다. 즉, 알고리즘의 성능을 설명하는 것입니다. 알고리즘의 로직을 코드로 구현할 때 시간복잡도를 고려한다는 것은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'를 뜻합니다. 시간복잡도는 주로 'Big-O 표기법'을 사용해 나타냅니다.

 

2. Big-O 표기법

[시간 복잡도를 표기하는 방법]

Big-O 표기법은 일반적으로 입력 크기 측면에서 알고리즘의 시간 복잡도를의 상한을 표현하는 방법입니다. 알고리즘이 수행하는 작업 수에 대한 최악의 시나리오를 설명합니다. 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용됩니다. 아래 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법입니다.

 

• Big-O(빅-오) 👉🏻 상한 점근
• Big-Ω(빅-오메가) 👉🏻 하한 점근
• Big-θ(빅-세타) 👉🏻 그 둘의 평균

[Big-O 표기법의 종류]

Big-O Complexity Chart / 출처 : https://www.bigocheatsheet.com/

• O(1)
  • 일정한 복잡도(constant complexity)라고 합니다.
  • 입력값이 증가하더라도 시간이 늘어나지 않습니다.
  • 문제를 해결하는 데 오직 한 단계만을 처리합니다.
• O(n)
  • 선형복잡도(linear complexity)라고 부릅니다.
  • 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다.
  • 문제를 해결하기위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.

**[another_O_n_algorithm]
입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가합니다. 이 알고리즘은 O(2n) 이라고 표현하겠다 라고 생각할 수 있습니다. 그러나, 사실 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기합니다. 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기합니다.

 

• O(log n)
  • 로그 복잡도(logarithmic complexity)라고 부릅니다.
  • Big-O표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.
  • 문제를 해결하는 데 필요한 단계들이 연산마다 특정 요인에 의해 줄업듭니다. 
• O(N log N)
  • 문제를 해결하기 위한 단계의 수가 N*(log2N) 번 만큼의 수행시간을 가진다. (선형로그형)
• O(N^2)
  •  2차 복잡도(quadratic complexity)라고 부릅니다.
  • 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.
  • 예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(N^2)이라고 표현합니다.
• O(2^N)
  • 기하급수적 복잡도(exponential complexity)라고 부릅니다.
  • Big-O 표기법 중 가장 느린 시간복잡도를 가집니다.

 

[시간 복잡도를 구하는 방법]

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

 

3. 자료구조 비교

출처 : https://www.bigocheatsheet.com/

 

3. 정렬 알고리즘 비교

출처 : https://www.bigocheatsheet.com/