이진 탐색 알고리즘의 재귀적 구현 이진 탐색의 알고리즘을 재귀적으로 구현해 보았다. 재귀적으로 구현해 성능은 좋지 않다. 이 알고리즘에서는 재귀적 성격을 다음의 반복적인 패턴에서 찾을수 있다. 1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인. 2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 재탐색. 그리고 탐색 대상을 찾을때 까지 위 2가지 패턴을 반복한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public class b_04_RecursiveBinarySearch { static int BSearchRecur(int ar[], int first, int last, int target) { if(first > last)//재.. 이진 탐색 알고리즘의 재귀적 구현 이진 탐색 알고리즘의 재귀적 구현 재귀의 활용(피보나치 수열) 재귀의 활용(피보나치 수열) 재귀의 활용(피보나치 수열) 피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열로서 다음과 같이 전개가 된다 앞의 수 두개를 더해서 현재의 수를 만들어가는 수열이다. 그래서 처음 0과 1이 주어진 상태에서 다음의수 1을 만들어 가게 된다. 수열의 1번째 위치의 값은 0을 반환 수열의 2번째 위치의 값은 1을 반환 3번째 이상 n번째 부터는 n-1번째+n-2번째의 값의 합을 반환 한다. 이를 코드로 구현해보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class b_03_FibonacciFunc { static int Fibo(int n) { if(n==1)//수열의 1번째 위치의 값은 0을 반환 return 0; else if(n==2)//수열의 2번째 위치의 값은 1을 반환 ret.. 재귀의 활용(피보나치 수열) 1. 재귀의 활용(피보나치 수열) 재귀(Recursive) 1. 재귀(Recursive): - 함수(메소드) 내에서 자기자신을 다시 호출하는것을 의미한다. - 완료되지 않은 함수를 다시 호출하는것 - 제일 첫번째로 호출된 함수가 가장 마지막에 종료가 되는 특성 - 탈출 조건이 있어야한다. 없으면 무한 반복 한다. 1) 예시1 - 간단한 출력 12345678910111213141516public class b_01_Recursive { static void Recursive(int num) { if(num 재귀(Recursion) 재귀(Recursion) 성능분석 방법(빅오 표기법) 모든 경우에 있어서 항상 우월한 성능을 보이는 자료구조와 알고리즘은 없다. 그래서 자료구조와 알고리즘을 분석하고 평가 할 수 있어야 한다. 알고리즘의 성능 분석 평가 요소에는 2가지 복잡도가 있다. 복잡도란: 알고리즘의 성능을 객관적으로 평가하는 기준이다. 1. 시간복잡도(time complexity): - 알고리즘이 속도가 얼마나 빠른가? CPU가 얼마나 많은 일을 하는가? - 속도에 해당하는 알고리즘의 수행시간 분석결과를 가리킨다. - 실행에 필요한 시간을 평가한것인데, 실제 시간은 여러 상황과 조건에 따라 달라질수 있다. 그래서 객관적 판단 기준인 연산횟수로 시간 복잡도를 구한다. 1) 시간 복잡도의 평가 방법 - 알고리즘에서 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다. - 처리해야 할 데.. 이전 1 ··· 36 37 38 39 40 다음
