재귀함수 recursive algorithm 과제

< Homework #1 >

 

1. 아래 문제에 대한 recursive algorithm 을 설계하고 시간복잡도를 분석하세요

(반복문 사용 금지 , 재귀호출만 사용하기)

 

• 배열에서 최솟값 찾기

 

• 배열의 원소의 총합 계산하기

 

• Selection Sort

 

 

 

2. Pancake Sorting

 

• 교재 Exercise 9(a),(b) in Chapter 1 of [E] (page 49)

 

• (c) 는 옵션

 

 

Homework #1 (3/26까지)

 

• 아래 문제에 대한 recursive algorithm을 설계하고

시간복잡도를 분석하세요

(반복문 사용 금지, 재귀호출만 사용하기)

• 배열에서 최솟값 찾기

• 배열의 원소의 총합 계산하기

• Selection Sort

• Pancake Sorting

• Exercise 9(a),(b) in Chapter 1 of [E] (page 49)

• (c)는 옵션

 

 

 

🌟1) 배열에서 최솟값 구하기 -> 재귀

 

< 파이썬 >

def min(x, y):

if x < y :

return x

else:

return y

 

def min_array(array, len):

if len == 1:

return array[0]

else:

return min(array[len - 1], min_array(array, len - 1))

 

temp_array = [33, 44, 1, 66, 139, 90, 45, 23]

 

print (min_array(temp_array, len(temp_array)))

 

시간복잡도는 O(n)

 

# 분석

 

주어진 Python 코드에서 함수 의 시간 복잡도 min_array는 O(n)입니다. 여기서 n은 입력 배열의 길이입니다.

 

이 min_array함수는 재귀를 사용하여 배열에서 최소 요소를 찾습니다. 각 재귀 호출에서 함수는 입력 배열의 길이를 1씩 줄이고 자신을 재귀적으로 호출합니다. 이 함수는 또한 min각 재귀 호출에서 함수를 한 번 호출합니다. 함수는 자신을 재귀적으로 n번 호출하므로(여기서 n은 입력 배열의 길이임) 함수의 시간 복잡도는 min_arrayO(n)입니다.

 

이 min함수는 입력 값에 관계없이 일정한 양의 작업을 수행하므로 시간 복잡도는 O(1)입니다.

 

따라서 주어진 코드의 전체 시간 복잡도는 O(n)이며, 이는 함수의 시간 복잡도에 의해 지배됩니다 min_array.

 

 

 

 

 

 

 

🌟2) 배열의 원소의 총합 계산하기 -> 재귀

 

< 파이썬 >

def recursive(numbers):

print("receive : ", numbers)

if len(numbers) < 2:

print("end!!")

return numbers.pop()

else:

pop_num = numbers.pop()

print("pop num is : ", pop_num)

print("rest list is : ", numbers)

sum = pop_num + recursive(numbers)

print("sum is : ", sum)

return sum

 

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(recursive(numbers))

 

 

# 분석

 

이 recursive함수는 재귀를 사용하여 목록의 요소 합계를 계산합니다. 각 재귀 호출에서 함수는 목록에서 마지막 요소를 제거하고 나머지 목록을 사용하여 자신을 재귀적으로 호출합니다. 이 함수는 또한 일정한 양의 작업을 수행합니다. 즉, 제거된 요소를 나머지 요소의 합에 추가합니다. 함수는 자신을 재귀적으로 n번 호출하므로(여기서 n은 입력 목록의 길이임) 함수의 시간 복잡도는 recursiveO(n)입니다.

 

각 재귀 호출에서 수행되는 일정한 작업량은 고정된 작업량이며 입력 목록의 크기에 의존하지 않기 때문에 시간 복잡도에 영향을 미치지 않습니다.

 

따라서 주어진 코드의 전체 시간 복잡도는 O(n)이며, 이는 함수의 시간 복잡도에 의해 지배됩니다 recursive.

 

 

🌟3)

 

※ 새로 알게 된 파이썬 문법

lst = [11] + [22]

print(lst)

 

< 코드 >

 

def selectionSort(xs):

if xs != []:

smallest = min(xs)

xs.remove(smallest)

return [smallest] + selectionSort(xs)

else:

return []

 

lst = [11, 22, 33, 44, 55, 9 ,1, 3]

print(selectionSort(lst))

 

# 분석

주어진 Python 코드에서 함수 의 시간 복잡도 selectionSort는 O(n^2)입니다. 여기서 n은 입력 목록의 길이입니다.

 

이 selectionSort함수는 재귀를 사용하여 선택 정렬 알고리즘을 사용하여 요소 목록을 정렬합니다. 각 재귀 호출에서 함수는 입력 목록에서 최소 요소를 찾아 목록에서 제거합니다. 이 함수는 또한 나머지 목록과 함께 자신을 재귀적으로 호출하고 최소 요소를 정렬된 목록에 연결합니다. 함수는 자신을 재귀적으로 n번 호출하고(여기서 n은 입력 목록의 길이임) 각 재귀 호출에서 최소 요소를 찾기 위해 선형 검색을 수행하고 최소 요소를 제거하기 위해 선형 시간을 수행하므로 시간 복잡도는 다음과 같습니다. 함수 selectionSort는 O(n^2)입니다.

 

각 재귀 호출에서 수행되는 일정한 작업량은 고정된 작업량이며 입력 목록의 크기에 의존하지 않기 때문에 시간 복잡도에 영향을 미치지 않습니다.

 

따라서 주어진 코드의 전체 시간복잡도는 O(n^2)이며 함수의 시간복잡도가 지배적이다 selectionSort.