알고리즘 분석(SET, INDEXOF, ADD, REMOVE)

프로파일링 또는 성능 분석은 프로그램의 시간 복잡도 및 공간, 특정 명령어 이용, 함수 호출의 주기와 빈도 등을 측정하는 동적 프로그램 분석의 한 형태이다.  참조: 위키피디아

 

문제점, 모두 구현해봐야 하고 컴퓨터 성능에 의존, 데이터에 의존.

 

해결책 : 알고리즘 분석

구현하지 않고도 알고리즘을 비교

 

간단한 알고리즘은 몇 가지 범주로 구분상수 시간, 선형, 이차

 

선택 정렬

/**
 * 
 */
package com.allendowney.thinkdast;

import java.util.Arrays;

/**
 * @author downey
 *
 */
public class SelectionSort {

   /**
    * Swaps the elements at indexes i and j.
    */
   public static void swapElements(int[] array, int i, int j) {
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
   }

   /**
    * Finds the index of the lowest value
    * between indices low and high (inclusive).
    */
   public static int indexLowest(int[] array, int start) {
      int lowIndex = start;
      for (int i = start; i < array.length; i++) {
         if (array[i] < array[lowIndex]) {
            lowIndex = i;
         }
      }
      return lowIndex;
   }

   /**
    * Sorts the cards (in place) using selection sort.
    */
   public static void selectionSort(int[] array) {
      for (int i = 0; i < array.length; i++) {
         int j = indexLowest(array, i);
         swapElements(array, i, j);
      }
   }

   /**
    * @param args
    */
   public static void main(String[] args) {
      int[] array = {2, 5, 6, 1, 3};
      selectionSort(array);
      System.out.println(Arrays.toString(array));
   }

}

indexLowest 메서드는 선형, swapElements 메서드는 이차

 

총 연산 횟수는 n²에 비례

 

빅오 표기법 : 알고리즘을 분류하는 방식 ( 모든 선형 알고리즘 o(n), 모든 이차 알고리즘 o(n²))

 

 

@Override
public T set(int index, T element) {
   //인덱스를 검사하는 코드의 반복을 피해야 한다.
      
   return null;
}

@Override
public int indexOf(Object target) {
   // TODO: FILL THIS IN!
   return -1;
}

 

 

@Override
public boolean add(T element) {

   return false;
}

@Override
public T remove(int index) {
   // TODO: FILL THIS IN!
   return null;
}

REFERENCE

GitHub - yudong80/ThinkDataStructures: LaTeX source and supporting code for Think Data Structures: Algorithms and Information Re