Midterm claim #2: 6번 문제 시간초과 관련

[shuuki4]

fiba_aux 관련 질문입니다.
제가 사용한 컴퓨터에서 제가

Fixpoint fiba_aux (n:nat) : nat*nat :=
 match n with
 | 0 => (3, 2)
 | 1 => (3, 3)
 | S (S n2 as n1) => match fiba_aux n1 with
                     | (a,b) => (a/2+b, a)
                     end
 end.

같은 식으로 fiba_aux를 정의했는데, 너무 시간이 오래 걸리고, 오류도 나서 이러한 방식으로 정의를 못했습니다.
조교님이 말씀하시길 저렇게 정의하면 a, b를 호출하는 과정에서 내부적으로는 fiba_aux n1을 불러서 결국 exponential 하게 계산 되는 것이라고 말씀하셨는데,
다른 친구들의 말을 들어보니 이런 방식으로 정의해서 문제를 풀었고
심지어 저도 저 코드를 제 노트북으로 똑같이 돌렸는데 제 노트북에서는 linear time으로 돌아가는 것을 확인하였습니다.
이 문제는 왜 일어나는건가요? 이 문제 때문에 여기에 정말 많은 시간을 썼고 결국 후속 문제에 접근도 못했는데...

[YeongjinOh]

저도 이 문제에 대해 문의드리려고 메일을 보냈는데 조교님께서 아직 답장이 없으시네요.
확인 부탁드립니다.

[jeehoonkang]

@gilhur 교수님과 상의해보고 답변드리겠습니다.

[jeehoonkang]

• 이의제기하신 분: 2014-12254(@shuuki4) 2010-13397(@YeongjinOh)
• 상태: 오늘(20160426) 수업시간에 교수님께서 공지하실 예정입니다.

[YeongjinOh]

@jeehoonkang 2010-13397입니다.

[shuuki4]

@jeehoonkang 2014-12254 입니다.