점화식

점화식 또는 재귀 관계식은 재귀와 초깃값을 사용하여 값의 열을 정의하는 방정식입니다. 점화식에는 선형, 비선형, 동차, 비동차, 일차 또는 고차가 있습니다. Wolfram|Alpha는 다양한 종류의 점화식을 풀고 주어진 수열이 만족하는 재귀 관계식을 구할 수 있습니다. 점근적 경계를 구할때 마스터 정리 또는 Akra-Bazzi 방법등이 쓰입니다.

점화식을 풉니다.

재귀 관계식과 차분 방정식의 닫힘식의 해를 구합니다.

점화식을 풉니다:

g(n+1)=n^2+g(n)

초깃값을 지정합니다:

g(0)=1, g(n+1)=n^2+g(n)
f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=2

q-차분 방정식을 풉니다:

a(q n)=n a(n)

점화식 찾기

재귀 관계식을 추론하여 수열 또는 함수 열을 모델링합니다.

주어진 수열에 만족하는 점화식을 찾습니다:

피보나치(n) 점화식

함수열이 만족하는 점화식을 구합니다:

라게르 다항식의 점화식

점근적 경계

분할 정복 알고리즘을 분석할 때 처럼 지표에 대한 척도변환과 관련된 점화식에 대한 점근적 경계를 구하세요.

점화식에 대한 점근적 경계를 찾으세요:

T[n]==T[n/2]+1

바닥 함수와 천장 함수를 이용해 지표를 반올림하세요:

f(n)=f(floor(n/2))+f(ceiling(n/2))+n

점화식이 완전하게 풀어지지 않더라도 점근적 경계를 계산하세요:

a[n] = n^2 + n^5 + Log[n] + 18 a[n/5] + 13 a[n/3]
f_n = logn + 18 f_(n/5) + 13 f_(n/25)
r(k) = k^2 + log(k) + 49 r(k/6) + 29 r(k/3)

관련 예제

  • Computational Complexity
  • 미분 방정식
  • 수열