시간복잡도

시간복잡도란?

효율적인 방법을 고민한다는 것

효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성

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

일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측

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

시간 복잡도 유형

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

Big-θ(빅-세타) : 보통일 때 연산횟수를 나타낸 표기법

Big-O(빅-오) : 최악일 때 연산횟수를 나타낸 표기법

1. O(1) : 일정한 복잡도, 입력값이 증가하더라도 시간이 늘어나지 않음
2. O(n) : 선형 복잡도, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
3. O(log n) : 로그복잡도, O(1)다음으로 빠른 시간복잡도를 가짐
4. O(n2): 2차복잡도, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
5. O(2n): 기하급수적 복잡도 , 가장 느린시간복잡도를 가짐

연산횟수 계산방법

연산횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

시간 복잡도 도출 기준

1. 상수는 시간복잡도 계산에서 제외

   3N = N 비슷

2. 가장 많이 중첩된 반복문의 수행횟수가 시간복잡도의 기준이 됨

   N, N제곱