알고리즘 공부 시작한 뉴비가 질문하기 란이 없어서 여기에 글 써봅니다.
강의 슬라이드의 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]에 할당하는 것은 연산으로 계산하지 않으셨는데 어떤 이유에서인지 잘 모르겠습니다.
comment