Java 기반 클라우드 융합 개발자 과정 - KH 정보교육원/10월
22.10.21 - [ 플러스 알파 ] 재귀함수, 시간 복잡도(빅오표기법)
giggs
2022. 11. 9. 14:11
-- INDEX --
| 1. 재귀 함수 | 2. 시간 복잡도 |
| 재귀호출이란? 재귀호출 예시 |
알고리즘 평가 요소 중 수행 시간 빅오표기법 ( 최악의 경우의 수행 시간 ) |
1. 재귀 호출 ( recursive call )이란?
- 함수 내부에서 함수가 자기 자신을 또다시 호출하는 행위를 의미합니다.
- 이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되게 됩니다.
- 따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.
- 재귀 호출은 알고리즘이나 자료 구조론에서는 매우 중요한 개념 중 하나
- 재귀 호출을 사용하면 복잡한 문제도 매우 간단하게 논리적으로 접근하여 표현할 수 있습니다.
> 메서드 안에서 자기 자신을 다시 호출하는 것
> 메서드를 호출하면 – 스택 메모리에 계속 쌓인다.
> 메서드 실행 끝나면 없어짐
> 리턴해서 돌아가고 리턴해서 돌아가고
> 증감식 필요
1-1 : 함수란?
- 하나의 작업을 수행하기 위해 독립적으로 설계된 프로그램 코드의 집합입니다.
- C 프로그램은 이러한 함수들로 구성되며, 포함된 함수들을 사용하여 프로그램의 목적을 달성하게 됩니다.
1-2 : 재귀호출 예시
- 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함하여야 한다.
- 특정 조건이 되면 재귀 호출 안 하게 만들고 싶다. - if문으로 작성해 보았다.
- 입력받은 숫자부터 10까지 출력하는 재귀 함수 -
2. 시간 복잡도 ( Time Complexity )
- 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말한다.
- 알고리즘을 평가할 때는 2가지를 사용한다.
- 수행 시간에 해당하는 것이 시간 복잡도 Time Complexity
- 메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity
2-1 : 빅-오 표기법(Big-O)이란?
연산 횟수를 카운팅 할 때는 3가지를 사용한다.
- 최선의 경우 Best Case
- 최악의 경우 Worst Case
- 평균적인 경우 Average Case
알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워 지므로
알고리즘의 성능을 파악할 때는 최악의 경우로 판단한다.
이 때 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 한다.
2-2 : 빅-오 표기법
- O(1) (Constant)
- 프로그램에서 1라인이 실행되는 경우, 1이라고 표현
- O(log₂ n) (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 경우, 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.
- O(n) (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가할 경우, 1차원 for문 즉, 반복문이 N번만큼 반복할 경우
- O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘, 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적
- O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 경우, 이중 루프가 대표적
- O(2ⁿ) (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 경우, 피보나치 수열과 재귀가 역기능을 할 경우가 대표적
# n이란 입력되는 데이터를 의미
- n 자리에 1~10 만 올 수 있다고 한다면
- 시간 복잡도가 n인 경우에는 – 운이 좋으면 1번에 끝낼 수도 있고, 나쁘면 10번 만에 끝낼 수 있다.
- 시간 복잡도가 n^2인 경우에는 – 운이 좋으면 1번에 끝낼 수도 있고, 나쁘면 100번 만에 끝낼 수 있다.
- 1~1000 사이의 숫자가 온다고 제한을 준다면 --- 중첩 반복문 써도 상관없다.
- 1~10000 사이의 숫자가 온다고 제한을 준다면 --- 시간 복잡도 계산하여야 한다.