시간복잡도 ☎

주어진 문제를 해결하기 위한 연산 횟수를 말한다.

 

일반적으로 파이썬 프로그램에서는 2000만번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다.

 

시간 복잡도 유형

1) 빅-오메가( Ω(n) ) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법

2) 빅-세타( θ(n) ) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법

3) 빅-오( O(n) ): 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

ex)

 

빅 오메가의 시간 복잡도는 1번, 빅-세타 표기법의 시간 복잡도는 N/2번, 빅-오 표기법의 시간 복잡도는 N번입니다.

 

빅-오 표기법( O(n) )을 기준으로 수행 시간을 계산하는 것이 좋다.

 

- 종류

O(1) - Constant Time(상수)

일정한 시간이 걸리는 알고리

 

O(n) - Linear Time(선형)

입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘이다.

n이 1늘어날 때마다 처리 시간이 1증가하여 처리 시간이 선형적으로 증가.

 

O(log n) 

이진검색이 대표적인 예이다

 

ex) 100 중에 원하는 숫자를 고를 때

50보다 큰가? Yes... -> 75보다 큰가?.... NO .......................

 

O(n^2) - Quardratic Time

이중 포문이나 배열의 크기가 커질수록 나타나는 복잡도

-> for문이 10개 있다고 해서 그럼 더 느려지는 걸로 의미되는가? No for문 하나를 상수처리해서 제곱으로 사용되므로 무시된다.

 

O(2^N) - Exponential Time

2n과 같이 n이 하나씩 증가할 때마다 걸리는 시간이 배로 증가하기 때문에

Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
재귀 함수로 구현하는 피보나치(Fibonacci) 수열로 비유할 수 있다.

 

출처 : https://velog.io/@do_dam/%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity-Big-O-%ED%91%9C%EA%B8%B0%EB%B2%95-%ED%99%9C%EC%9A%A9