[Python] 재귀호출, 시간복잡도

<목차>

1. 재귀호출
2. 시간복잡도
3. 정렬★★★
4. 배열★
5. 연결리스트★
6. 스택★
7. 큐★
8. 그래프★
9. 트리★

---

#자료구조 : 데이터를 구조적으로 관리 및 표현하는 방식으로, 필요한 기능을 가능하게 하는 기술

- 최소한의 메모리 사용 가능 (메모리는 적게 쓰고)

- 처리 속도 향상으로 실행시간 단축 (속도는 빠르게!)

---

1. 재귀함수 : 자기가 자기를 호출

- 동일한 문제를 계속해서 간단하고 쉽게 반복 수행하여 문제를 해결함.

- 동일 함수의 복사본이 스택 메모리에 생성되고 쌓임.
    ~ 재귀함수는 기본함수와 별개의 함수

- 호출한 함수가 모두 return 되어야 되돌아와서 실행함.

- 재귀호출의 종료 조건이 필요함.★★★
    ~ 종료 조건이 없으면 무한 반복됨.

- 재귀호출할 때 함수가 메모리에 쌓이므로 메모리 용량 초과 주의 필요함. #stack overflow (메모리 용량 초과)
    ~ 성능에서 좋지 않으나 코드는 간결해짐.
    ~ 오히려 다른 사람이 보기에 어려울 수 있음.

- 팩토리얼, 피보나치 수열 등의 경우에 사용됨.

---

재귀함수 vs 반복문 - 누적 합계

 

#1부터 n까지 더하기 (누적합계) - 재귀함수

def my_sum(n) :

    if (n > 1) :
        return n + my_sum(n-1)
    else :
        return 1 #종료 조건

a = int(input("숫자를 입력하세요. "))
print(my_sum(a))

#1부터 n까지 더하기 (누적합계) - 반복문

a = int(input("숫자를 입력하세요. "))
result = 0

for i in range(1, a+1) :
    result = result + i

print(result)

---

재귀함수 vs 반복문 - 수 출력

#1부터 n까지 출력 -  재귀함수

def number_print(n) :
    if (n>=1) :
        number_print(n-1)
        print(n)

a = int(input("숫자를 입력하세요. "))
number_print(a)

#1부터 n까지 출력 -  반복문

a = int(input("숫자를 입력하세요. "))

for i in range(1, a+1) :
    print(i)

---

재귀함수 vs 반복문 - 팩토리얼

#팩토리얼 - 재귀함수

def factorial(n) :

    if (n > 1) :
        return n *  factorial(n-1)
    else :
        return 1 #종료 조건

a = int(input("숫자를 입력하세요. "))
print(factorial(a))

#팩토리얼 - 반복문

a = int(input("숫자를 입력해 주세요. "))
result = 1

for i in range(1, a+1) :
    result = result * i

print(result)

---

재귀함수 vs 반복문 - 피보나치 수열

#피보나치 수열 - 재귀함수

def fib(n) :
    if n <= 2 :
        return 1

    else :
        return fib(n-1) + fib(n-2) #★★★

print(fib(5))

#피보나치 수열 - 반복문

def fib(n) :
    a, b = 1, 1
    if n == 1 or n == 2 :   
        return 1

    for i in range(1, n) :
        a, b = b, a+b

    return a

print(fib(5))

---

재귀함수 vs 반복문 - 최대공약수

#최대공약수 - 재귀함수

def gcd(a, b) :
    if a % b == 0 :
        return b
    else :
        return gcd(b, a%b)

print(gcd(16, 12))

**유클리드 호제법
- 두 자연수 A, B (A>B)일 때 A를 B로 나눈 나머지를 R이라고 할 때 A, B의 최대공약수는 B, R의 최대공약수와 동일함.
    ~ 13, 11 => 11, 2 => 2, 1 => 1, 1 => 1
    ~ 16, 12 => 12, 4 => 4, 0 => 4

#최대공약수 - 반복문

a = 10
b = 12

for i in range(min(a,b), 0, -1) :  #두 수 중 작은 수부터 내려감
    if (a%i == 0 and b%i == 0) :
        print(i)
        break

---

재귀함수 vs 반복문 - 문자열 거꾸로 출력

#문자열을 거꾸로 출력하기 - 재귀함수

def reverse_str(str) :
    size = len(str)

    if size == 1 : #종료조건
        return str
    
    else :
        return reverse_str(str[1 : ]) + str[0]
        
print(reverse_str("hello"))

 

#문자열을 거꾸로 출력하기 - 반복문

str = "hello"
result = ''

for i in str :
    result = i + result

print(result)

---

재귀함수 vs 반복문 - 2진수

#n 정수를 입력 받아 2진수로 출력하기 - 재귀함수

def bin(n) :
    if n < 2 :
        return n 

    else :
        return str(bin(n//2)) + str(bin(n%2))

print(bin(10))

*****강사님 코드*****

def bin(n) :
    if n == 0  :
        pass
    
    else :
        bin(n//2)
        print(n%2, end = '')

bin(10)

 

#n 정수를 입력 받아 2진수로 출력하기 - 반복문

a = 10
result = ""

while a > 0 :
    result = str(a%2) + result
    a = a // 2

print(result)

---

*복잡도
- 공간 복잡도 : 메모리 관련
- 시간 복잡도 : 속도 관련
    ~ 표기법
        1. 빅오메가 : 제일 빠른 값
        2. 빅세타 : 평균 속도
        3. 빅오 : 제일 느린 값

---

2. 시간복잡도

- 알고리즘의 수행 시간을 분석할 때 사용함.

- 연산 횟수를 세어 예측 가능함.

- 주로 빅오 표기법 사용함.
    ~ 최악의 시나리오로 계산함. (제일 느린 값)
    ~ 최고차항만 표기함.(디테일한 수식은 필요 없음)
    ~ 최고차항의 계수는 생략함.(디테일한 수식은 필요 없음)
    ~ 고려 요소는 반복, 조건문, 재귀호출

*빅오 표기법(빠른 순서대로 나열)

①O(1) - 상수시간 
    - 입력 n에 상관없이 일정한 연산을 수행함.(변수대입연산)
        ex)화면 출력(print) 

def printNum(list) :
    print(list[0])
    print(list[1])

②O(log n) - 로그시간
    - 입력 n 값이 커질 때 연산 횟수가 log n 비례하여 증가하는 연산을 수행함.
        ex) 이진트리의 탐색, i*2씩 증가하는 반복

def printNum(n) : #8을 넣으면 3번 출력(log₂2³ -> 3)
    i = 1
    while i < n :
        print(i)
        i = i*2

③O(n) - 선형시간
    - 입력 n 값이 커질수록 연산 횟수가 n에 비례하여 증가하는 연산을 수행함.
        ex₁) 1씩 증가하는 반복문

def printNum(n) :
    for i in range(0, n) :
        print(i)

                     
        ex₂) 1씩 증가하는 반복문이 2번  #주어진 n번이 2번이므로 O(2n)이지만 시간복잡도는 계수를 생략하여 표기함.O(n)

def printNum(n) :
    for i in range(0, n) :
        print(i)
    for j in range(0, n) :
        print(j)

④O(n²) - 2차 시간
    - 입력 n값이 커질수록 연산 횟수가 n²에 비례하여 증가하는 연산을 수행함.
        ex) 1씩 증가하는 반복문의 이중반복문 #바깥 반복문 n번, 안쪽 반복문 n번 / 총 n*n(n²)번수행

def printNum(n) :
    for i in range(0, n):
        for j in range(0, n) :
            print(i*j)

⑤O(2ⁿ) - 지수시간
    - 입력 n 값이 커질수록 연산횟수가 2ⁿ에 비례하여 증가하는 연산을 수행함.
        ex) 한 번 호출할 때마다 두 번씩 호출하는 재귀함수(피보나치)

def fib(n) :
    if n<2 :
        return 1
    else :
        return fib(n-1) + fib(n-2)