1) 루프 : 루프 안의 구문들의 수행 시간 곱하기 반복 횟수 값이 된다.
2) 중복 루프 : 전체 수행 시간은 각각의 루프의 수행 시간을 계산해서 구한다.
3) 연속된 구문들 : 각 구문의 복잡도를 더한다.
4) if-then-else 구문 : 조건문 수행 시간의 then 부분 또는 else 부분 중에 더 오래 걸리는 쪽 시간을 고려. 즉, 더한 경우이다.
5) 로그형 복잡도 : 어떤 알고리즘의 문제의 크기를 일부(보통은 1/2)를 줄이는데 일정한 시간이 걸린다면 o(logn)이다.
ex) 이진 트리
-최악의 경우, 중간의 경우, 최선의 경우 고려하여 더 큰 애를 선택하면 된다. max( f(n) , g(n) )
---
* 재귀(recursion) 와 백트래킹(backtracking)
재귀는 왜 사용할까?
- 재귀는 수학으로부터 빌려온 유용한 기법이다.
재귀 코드는 반복코드보다 짧고 작성하기 쉽다. 일반적으로 루프느는 컴파일 시점이나 인터프리트 될 때 재귀함수로 바뀐다.
- recusrion의 반대 형태 : 수학적 귀납법
ex) 자연수n에 대해 증명하기 (큰 문제를 풀때 더 작은 문제로.. 더 작은 문제로 풀어서 맞다고 가정)
모든 자연수는 짝수 아니면 홀수다.
n=1 -> 증명
n=i 일때 ->가정
n = i+1 일때 증명하면 다 증명되었다고 하는 것
재귀적 방법은 자신의 복사본을 호출하여 더 작은 문제를 풀게하여 문제를 해결하는 방식이다.
이를 재귀 단계라고 부른다.
재귀 단계는 더 많은 수의 재귀 단계를 만들 수 있다.
중요한 것은 재귀가 확실히 종료하게 해야 한다는 점이다.
작은 문제의 서열은 결국 기본 경우로 수렴해야 한다.
ex) 팩토리얼 함수
0! = 1
6! = 6 * 5 * 4 * 3 * 2 * 1
n! = n * (n-1)!
function f(n) {
if (n <= 1) {
return 1 // 종료 조건
}
return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050
재귀 함수는 하위 작업을 수행하도록 자기 자신을 호출하여 작업을 수행한다.
어느 단계에 이르러서는, 자기 자신을 호출하지 않고도 수행할 수 있는 하위 작업을 수행한다.
이렇게 함수가 재귀 호출하지 않는 것을 기본 경우(base case)라고 하고,
함수가 자기 자신을 호출해서 하위 작업을 수행하는 것을 재귀 경우(recursion step)라고 한다.
- 모든 재귀 함수는 base case 인 경우 종료해야 한다.
- 일반적으로 반복 해법이 재귀 해법보다 효율적이다. (재귀 호출에 따른 부가적인 메모리 요구 때문)
- 리커전으로 풀 수 있는 것은 반복적으로 풀 수도 있다는 것 ( 다 그런건 아님 )
- 어떤 문제들의 경우엔 눈에 띄는 반복적 알고리즘이 없을 수도 있다.
댓글