시간 복잡도

📌 시간 복잡도

시간 복잡도를 고려한다는 것
: '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'라는 말이다.

• 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

 

📌 Big-O 표기법

1. O(1)

: O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

• 일정한 복잡도 -> 상수항(0차식)

 

*예시

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

• 입력이 아무리 커져도 코드를 '딱 1번'만 실행함

 

2. O(n)

: O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또는 같은 비율로 증가하는 것을 의미한다.

• 예시: 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배 증가 시켰을 때 100초가 걸리는 알고리즘

 

3. O(log n)

: O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

• 예시: BST의 값 탐색
• BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.

 

4. O(n2)

: O(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

• n의 제곱수의 비율로 증가 -> 2차식

 

 

5. O(2n)

: O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

• 예시: 피보나치 수열

 

 

 

 

---

참고

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/