귀속 예제

1. 피보나치 수열 피보나치 수열, 예를 들어 1 1 2 3 5 8... 1항과 2항을 제외하고 모든 수열의 값은 전항과 전항의 가화이다. 함수로 전환하면 f(n)= f(n-1)+f(n-2)에서 n이 지정한 그 숫자의 값을 구한다.

private  static int func2(int n){
	 if(n==1 || n==2){
			return 1;
		}
	 else{
	 // 
		 return func2(n-1)+func2(n-2);
		 }
	 }

이 방법은 n회로 귀속되고 시간의 복잡도는 O(2^n)2이다. 수조가 점증 서열인지 아닌지를 판단하여 점증 함수func3를 실현하고arr수조가 점증 서열인지 아닌지를 판단하는 수조truefalse

private static boolean func3(int[] arr){
		
		return func3(arr,0,arr.length-1);
	}
	private static boolean func3(int[] arr,int i,int j){
		if(i+1>j){
			return true;
		}
		if (arr[i]>arr[i+1]){
			return false;
		}
		return func3(arr,i+1,j);
		
	}

3. 루트를 루트로 하는 단일 체인 테이블의 유효한 노드 수량을 되돌려 줍니다.먼저 체인 테이블 노드 클래스를 정의한 다음 메소드 노드 클래스를 작성합니다.

class Entry{
        int data;
        Entry next;

        public Entry(int data, Entry next) {
            this.data = data;
            this.next = next;
        }
    }

방법:

private int func4(Entry root) {
    	if(root==null){
    		return 0;
    	}else{
    		return 1+func4(root.next);
    	}
    }

테스트:

 public  void test02(){
        Entry root = new Entry(0, null);
        Entry n1 = new Entry(10, null);
        Entry n2 = new Entry(10, null);
        Entry n3 = new Entry(10, null);
        Entry n4 = new Entry(10, null);
        root.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        System.out.println(" :" + func4(root));
    }

4. 빠른 정렬(귀속 방법) 빠른 정렬의 시간 복잡도: O(log2n), 최악: O(n^2) 빠른 정렬이 질서정연할수록 효율도 낮아진다. 기본적인 질서정연한 서열에서 정렬을 하는 것은 정렬을 삽입하는 것이 더욱 빠르고 최적화된다. 데이터가 어느 정도 줄어들면 빠른 정렬 안정성을 삽입으로 대체한다. 불안정

// 
private static  void quickSort(int[] arr, int i, int j) {
        if(i > j)
            return;
        int l = partation(arr, i, j); // left == right
        // i l-1 
        quickSort(arr, i, l-1);
         // l+1 j 
        quickSort(arr, l+1, j);
    }
    
  // ， ， 
    private static  int partation(int[] arr, int l, int r) {
	 int val=arr[l];
	 while(ll && arr[r]>val){
			 r--;
		 }
		 //2. val l ， l++
		 if(ll && arr[l]