[알고리즘] 수행 시간

logn < n < nlogn < n^2 < n^3 < 2^n < n!

수행시간을 좌우하는 기준

• for 루프 반복 횟수
• 함수의 호출 횟수
• 특정 행의 수행 횟수

*n = A[] 배열의 원소 수

1. 상수시간 n

• 데이터 개수 n일때, n에 비례하는 시간이 소요됨
• n의 수가 증가할수록 오래걸림

sample1(A[ ], n) 
{ 
	k = ; 
	return A[k] ;
}

sample2(A[ ], n) 
{ 
	sum ← 0 ; 
	for i ← 1 to n
		sum← sum+ A[i] ;
		return sum ;
}

1. n^2

• n2에 비례하는 시간이 소요

sample3(A[ ], n) 
{ 
	sum ← 0 ; 
	for i ← 1 to n
		for j ← 1 to n 
			sum← sum+ A[i]*A[j] ; 
			return sum ;
}

sample4(A[ ], n) 
{ 
	sum ← 0 ; 
	for i ← 1 to n-1
		for j ← i+1 to n 
			sum← sum+ A[i]*A[j] ; 
			return sum ;
}

1. n^3

• n3에 비례하는 시간이 소요
• n의 수에 따가 기하급수적으로 시간이 오래 걸리게 된다.
• n^2와 같이 for문은 2개이지만, 이중 최대 값을 선정하는데 n만큼 소요된다. (⇒ 비교가 필요)

sample5(A[ ], n) 
{ 
	sum ← 0 ; 
	for i ← 1 to n
		for j ← 1 to n { 
			k ←A[1 ... n] 에서 임의로 [n/2]개 뽑을 때 이중 최대값 ; 
			sum ← sum + k ; 
	} 
	return sum ;
}