배열에서 최솟값을 찾는 것을 재귀로 만들고 그 시간 복잡도를 계산하려고 하는데
F(A[1..n], m)라는 함수(배열과 최솟값 변수 매개변수로)를
if(n=0) return m
else
if A(n)>m
F(A[1..n-1], A[m])
else
F(A[1..n-1], m)
혹은 그냥
F(A[1..n-1],min(A(n),m))
이라는 느낌으로 슈도코드를 짜보고 코딩을 해봤습니다.
문제는 보통 이런 경우의 T(n)을 어떻게 구해야할지 모르겠습니다.
if문으로 재귀함수가 실행되는 곳이 나뉘는데 각각 얼마나 실행되는지 모르는 상황이니 2*T(n/2)같은 건 안될 것 같고 한쪽의 실행 수를 r이라고 하면
T(n) = T(r)+T(n-r) 같은 느낌이 되어야 하는 걸까요? 그리고 O는 최악의 경우를 상정해야하니 r=n이고 T(n) = T(n)+T(0)=T(n)이라거나... 이건 재귀인데 감소되는 부분이 없어서 아닌 것 같은데 어떻게 풀어내야할지 잘 모르겠어서 조언을 구해봅니다.
