알고리즘 공부 시작한 뉴비가 질문하기 란이 없어서 여기에 글 써봅니다.

강의 슬라이드의 FIB2(n) 의사코드를 아래처럼 바꿔야 한다고 생각합니다.  

function FIB2(n)

    if n = 0 then return 0

    end if

    Let f[0, . . . , n] be an array of size n+1    # 슬라이드 오타 같습니다. 0~n 까지이니 n+1사이즈입니다.

    f[0] ← 0, f[1] ← 1

    if n>1 then                                       # 이 부분이 없으면 FIB2(1)에서 인덱스 에러가 날 것 같습니다. 

        for i = 2, . . . , n do

            f[i] ← f[i-1] + f[i-2]

        end for

    end if

    return f[n]

end function

바뀐 의사코드에 대하여 n>2인 경우에 필요한 연산은 if문의 n>1 부분의 비교 연산이 추가된 3(n-1)+4번이 되는것 같습니다.

궁금한점: 강의에서 f[0] ← 0, f[1] ← 1 부분의 할당은 모두 1번의 연산으로 계산하셨지만 f[i] ← f[i-1] + f[i-2] 부분에서는 f[i-1] + f[i-2]를 불러오고 계산하는 것 까지만 연산으로 간주하고 f[i]에 할당하는 것은 연산으로 계산하지 않으셨는데 어떤 이유에서인지 잘 모르겠습니다.