[자료구조] 간단한 알고리즘 시간복잡도 구하기

Array 에서 가장 큰 원소 구하기

def array_max(A:Array,n:int):    (1)
    current_max = A[0]           (2) 대입연산
    for i=1 to n-1:              (3)
        if current_max < A[i]:   (4) 비교연산
            current_max = A[i]   (*) 대입연산
    return current_max

• (1) input으로 A라는 Array와 n이라는 int타입 데이터를 받는다
  - 이때 n은 Array의 길이이다
• (2) current_max 에 A의 0 번째 값을 할당한다 -(수행횟수 = +1)
  -  모든 인풋값에 대하여 항상 수행한다
• (3) 1부터 n-1까지 반복하여 작업을 수행한다.
  - 연산은 하지않기에 수행횟수가 추가되지않는다.
• (4) 반복문을 돌때마다 한번씩 비교연산자를 수행한다 (수행횟수 = n-1)
• (*) if문에 조건이 충족할때만 수행한다 (얼마나 수행할지는 알 수 없다)

이경우의 WorstCase를 구하려면 어떻게 해야할까?!

(4)번의 조건문에 항상 걸려서 (*)을 수행하도록 만들어야 한다.

그런 조건을 수행할 수 있는것은 오름차순으로 정렬된 Array가 가능하다.

즉, (*)의 수행횟수가 (4)와 동일해진다 이를계산해보면

• T(n) = 2n-2 +1 = 2n-1

모든 짝수 더하기

** 나머지연산은 실제로는 수행횟수가 1번이 아니지만 1번으로 취급하고 계산합니다.

def sum(A:Array, n:int):  (1)
    sum = 0               (2) 할당연산
    for i=0 to n-1:       (3)
        if A[i]%2 == 0:   (4) 나머지연산 + 비교연산
            sum += A[i]   (*) 더하기연산 + 할당연산
    return sum

• (2) sum에 0을 할당한다 (수행횟수 = +1)
• (3) n번 반복을 수행한다
• (4) n번 반복을 수행하는동안 나머지연산1번과 비교연산1본 총 2번 시행한다 (수행횟수 = 2n)
• (*) if문에 조건이 충족할때만 수행한다 (얼마나 수행할지는 알 수 없다)

이경우의 WorstCase를 구하려면 어떻게 해야할까?!

여기도 역시 (4)번의 조건문에 항상 걸려서 (*)을 수행하도록 만들어야 한다.

모든 요소가 짝수인 요소를 대입하여본다면

• T(n) = 1 + 2n + 2n = 4n + 1