자료구조 - 시간복잡도 관련 프로그램들

소개

대학 학부과정 자료구조 - 시간복잡도 관련 프로그램들 소스입니다.

컴파일 실행환경

모든 소스는 자바로 짜여져 있으며
jdk 1.3 을 사용했습니다.
hello wolrd 를 컴파일하여 실행시킬 줄만 아시면
기본적인 사용법은 충분합니다.

본문내용

1. f(x) = 시그마 a_i * x^i을 계산하는 알고리즘에 대하여
a. 이를 자바프로그램으로 표현하시오
b. 이 알고리즘에 대한 시간복잡도를 보이시오

2. 버블정렬을 조사하여 자바 프로그램으로 작성하고 이 알고리즘의 시간 복잡도를 각 줄 단위로 계산해 보이시오.

3. 아래 프로그램을 작성하여 실험 결과를 보이시오.
1) Fibonacci수를 처음부터 50번째까지의 수를 재귀 알고리즘을 사용하여 출력
2) HanoiTower문제에서 디스크 개수가 3, 4개일 때의 디스크 이동 순서를 출력

4. a, b가 양의 정수일 때, 곱 a*b의 값은 a를 b번 더한 것이다. 곱 a*b을 b에 대한 재귀적 정의로 나타내고 재귀 알고리즘으로 표현하라.

5. Ackerman함수는 음이 아닌 정수 m, n에 대하여 다음과 같이 재귀적으로 정의된다.
A(m, n)=2n if m=0
A(m, n)=0 if m≥1, n=0
A(m, n)=2 if m≥1, n=1
A(m, n)=A(m-1, A(m, n-1)) if m≥1, n≥2

1) A(2, 2)의 값을 구하시오.
2) A(3, 4)의 값을 2의 지수승으로 나타내시오.

참고자료

· 없음