시간 복잡도(Time Complexity) - 2

참고하였습니다 :

시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

https://www.youtube.com/watch?v=tTFoClBZutw&t=1135s

 

1장에서

시간복잡도

⇒ 알고리즘 성능이 얼마나 좋은가?

⇒ 실행시간이 얼마나 짧은가?

⇒ 실행횟수가 얼마나 작은가?

⇒ 실행횟수 식의 변수 N 이 무한하게 클때, 점근적 표기법으로 단순하게 보여지는 표현식

 

점근적 표기법 으로 시간복잡도를 표현.

이는 입력값 N → ∞ 일 때, 어떤 함수에 근접해지는지 분석. 한다고 했다.

 

 

 

아래의 코드를 보자

왼쪽의 코드는 정수배열 inputs 에 target 값이 있는지 확인하는 함수 이다.

오른쪽 그림 처럼, target 값이 배열의 앞쪽에 있으면 빨리 찾고, 끝쪽에 있으면 보다 늦게 찾을 것이다.

 

그래서 먼저 이렇게 2가지(Best,Worst) 경우로 구분 지을 수 있다.

• Best Case : 0번째에 존재 : 1번만에 찾음
• Worst Case : 마지막에 존재 or 존재하지 않음 : N번 걸림

 

우리는 추가 적인 이해를 위해 아래 2가지 점근적 표기법을 이해 해야 한다.

• Lower bound (하한선) = 빅 오메가 : Ω ⇒ 함수 실행시간은 아무리 빨라도 ??시간 이상이다.
• upper bound (상한선) = 빅 오 : O ⇒ 함수 실행시간은 아무리 오래 걸려도 ??에 비례 혹은 그 이하다.

## 추가 내용

하한선 기준으로 표현할수도 있고, 상한선 기준으로 표현할수도 있다. (둘다 맞는 표기법)

하지만, 실제 서비스와 현실세계 에서는 데이터가 N → ∞ 무한대에 가까워 지므로,

upper bound (상한선) = 빅 오 : O 표기법이 더 의미 있게 사용되며,

일반적으로 개발 세계에서, 점근적 표기법 = 빅 오 : O 표기법 이라 한다.

 

 

계속 해서 앞서 봤던 Best, Worst case 와 Lower bound (하한선), upper bound (상한선) 개념을 적용하여 이해해보자

Best Case : 0번째에 존재 : 1번만에 찾는 경우

• 빅 오메가 : Ω(1) ⇒ 함수 실행시간은 아무리 빨라도 상수(1)시간 이상이다.
• 빅 오 : O(1) ⇒ 함수 실행시간은 아무리 오래 걸려도 상수(1)에 비례 혹은 그 이하다.

 

Worst Case : 마지막에 존재 or 존재하지 않음 : N번 걸림

• 빅 오메가 : Ω(N) ⇒ 함수 실행시간은 아무리 빨라도 N시간 이상이다.
• 빅 오 : O(N) ⇒ 함수 실행시간은 아무리 오래 걸려도 N에 비례 혹은 그 이하다.

오른쪽 표 하단에

θ : 세타 노테이션 = tight bound (근접선) 이라고 한다.

⇒ 상한선과 하한선 표기방법이 모두 같을때, 즉 빅 오메가 = 빅 오 가 같을때 표현 할수 있다.

 

 

 

정리

각 case 별로 독립적으로 점근적 표기법을들 적용할 수 있다.