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
i | j |
---|---|
0 | n |
1 | n-1 |
2 | n-2 |
n-1 | 1 |