시간복잡도(Time Complexity)

int[] multiply(int[] inputs, int multiplier){
	int[] nums = new int[inputs.length]; //C1
	for(int i = 0;i<inputs.length;i++){ //C2
		nums[i] = inputs[i] * multiplier; //C3
	}
	
	return nums; //C4
}

이런 코드를 실행했을 때 실행 시간이 어느 정도일까?

 

실행 시간은 컴퓨터 성능에 따라 조금씩 편차가 있을 수 있음

 

이를 좀 더 객관적으로 나타내기 위해 실행시간이라는 개념 사용

실행 시간: 함수/알고리즘 수행에 필요한 스텝의 수

위 코드에서 각 라인 별 실행되는 스텝의 수를 하나의 상수라고 가정하면 실행 시간은 아래와 같이 계산할 수 있다

c1	1
c2	N+1	N번 수행되고 나서 루프를 빠져나가기 위한 검사를 한 번 더 수행하기 때문에 N+1회 수행
c3	N	for 루프를 배열의 크기만큼 반복하므로
c4	1

*여기서 N은 input의 크기

각각의 스텝 수 * 반복 횟수를 구해 더해야 하므로 실행시간 T(N)은 a*N + b 의 형태를 가짐

T(N) = c1 + c2*(N+1) + c3 * N + 1

=(c2 + c3) N + c1 + c2 + 1

=a*N + b

여기서 N이 작을 땐 실행 시간의 차이가 미미하므로 의미가 없음

N이 무한대로 발산할 때 걸리는 시간이 어떻게 될까?

a*N + b 에서 상수, 최고차항의 계수는 의미가 없으므로 제거

최종적으로 **함수의 실행 시간은 θ(N)**이 됨

이처럼, 임의의 함수가 N이 무한대로 커질 때 어떤 함수 형태에 근접해 지는 지 분석하는 방법을 점근적 분석(Asymptotic Analysis)

시간 복잡도: 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도

크기 N의 모든 입력에 대해 걸리는 최대의 시간

알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇 번인지 세는 것

시간 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘이라고 할 수 있음

주로 점근적 분석을 통해 실행 시간을 단순하게 표현

cf) 점근적: 가장 큰 영향을 주는 항만 계산한다는 의미로 아래와 같은 점근적 표기법을 통해 시간 복잡도를 나타낼 수 있음

• 최상의 경우(하한선): 오메가 표기법 (Big-Ω Notation) Ω
• 평균의 경우: 세타 표기법 (Big-θ Notation) Θ
• 최악의 경우(상한선): 빅오 표기법 (Big-O Notation) O