[자료구조]시간 복잡도

Jimin_Note·2022년 8월 22일
0

🌳자료구조

목록 보기
2/3
post-thumbnail

자료구조, 알고리즘의 시간복잡도

  1. 모든 입력에 대해 기본연산 횟수를 더한 후 평균
    ->현실적으로 불가능
    고려해야되는 입력 수가 너무 많음
  2. worstcase time complexity : 가장 안 좋은 입력(worstcase input)에 대한 기본 연산 횟수를 측정
    -> 어떤 입력에 대해서도 worstcase time complexity보다 수행시간이 크지 않다!무조건!

알고리즘 수행시간 = 최악의 입력에 대한 기본연산 횟수

최악의 입력에 대한 기본연산 횟수 구하기

T(n)=2n-1

.
.
.
algorithm1 arrayMax(A,n):
	a=A[0]
	for i in range(1,n):
		if a < A[i]: #1.여기는 무조건 들림
  	  		a=A[i] #2.if문이 false면 안넘어오지만 최악의 경우 무조건 넘어온다는 가정
#즉, for문 1번 돌때 1,2 총 2번 실행 2(n-1) = 2n-2
# a=A[0] 이 코드의 진행 횟수를 더하면 2n-1

ex.n=10 이면 2*10-1=19, 최악의 경우 최대 19번진행


T(n)=4n-1

algorithm2 sum1(A,n):
	sum = 0
    for i in range(1,n): 
    	if  A[i]%2==0: 
        #worst case:모든 값이 짝수
        	sum += A[i]
    return sum

n(n-1)/2*3+1

algorithm3 sum2(A,n):
	sum = 0
    for i in range(1,n): 
    	for j in range(i,n): 
    		sum += A[i]*A[j] #for문 돌 때 여기까지 3번의 연산이 이루어짐
            #여기까지 n(n-1)/2*3 이고 sum=0 진행횟수를 더하면 n(n-1)/2*3+1
    return sum
ij
0n
1n-1
2n-2
n-11
profile
Hello. I'm jimin:)

0개의 댓글