[algorithm] 알고리즘 02 : 알고리즘의 효율성 분석

자바로 쉽게 배우는 알고리즘 - part 2 : 알고리즘의 효율성 분석

알고리즘의 효율성

1. 시간의 효율성 [시간복잡도] : 처리시간의 효율성 -> 프로그래머가 주로 분석하는 대상
2. 공간의 효율성 [공간복잡도] : 사용하는 메모리의 효율성 -> 기술 발전으로 큰 문제가 안됨

알고리즘의 분석 체계

• 시간복잡도를 분석하는 것에 집중한다. 일단.
• 시간복잡도를 구성하는 요소는 다음과 같다

  1. 입력크기
  2. 실행시간측정단위 : 시스템 마다 기준이 달라서 측정하기가 애매함
  3. 증가차수 : 입력 값(N)크기에 따라 증가하는 실행시간의 증가 폭

     • log2N → N값이 4배 증가 할때 2배 시간 소요 (이상적)
     • N → N값이 4배 증가 할때 4배 시간 소요 (무난)
     • N^2 → N값이 4배 증가 할때 16배 시간 소요
     • 2^N → (최악) N값이 4배 증가 할때 4제곱 증가

시간복잡도

- 갑자기 난이도가 확 올라 감 ㄷㄷㄷ 수학

• 수식은 생략함
• 보통 시간 복잡도의 표기는 O-표기를 사용하여 표현

  O-표기로 표현한 대표적인 복잡도 범주 (n : 입력값)

  1. O(1) : 상수시간 → 입력값과 무관하게 시간이 걸리는 로직
  2. O(log n) : 로그시간 → 알고리즘을 반복할 때마다 문제의 크기가 상수 인수 만큼 작아짐, 효율적
  3. O(n) : 1차 선형 시간 → 입력크기에 비례하여 처리 시간이 걸리는 경우
  4. O(nlog n) : 로그 선형 시간 → 합병정렬 알고리즘
  5. O(n^2) : 2차 선형 시간 →
  6. O(n^3) : 3차 선형 시간 →
  7. O(2^n) : 지수 시간 →

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

비재귀 알고리즘 효율성

ComputeSquare.java 참조
ComputeCumulativeSum.java 참조

재귀 알고리즘의 효율성

ComputeFactorial.java 참조
BianarySearch.java 참조

part2 공부하면서 배운 소소한 java 팁

1. java ArrayList배열 sort 방법 (JDK 1.8 이후)

• 출처: https://hianna.tistory.com/569 [어제 오늘 내일:티스토리]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator; 

public class SortArrayList {    
  
  public static void main(String[] args) {         
    // ArrayList 준비        
    ArrayList<String> list = new ArrayList<>(Arrays.asList("C", "A", "B", "a"));
    System.out.println("원본 : " + list);  // [C, A, B, a]         
    // 오름차순으로 정렬        
    list.sort(Comparator.naturalOrder());        
    System.out.println("오름차순 : " + list);  // [A, B, C, a]         
    // 내림차순으로 정렬        
    list.sort(Comparator.reverseOrder());        
    System.out.println("내림차순 : " + list); // [a, C, B, A]                
    // 대소문자 구분없이 오름차순 정렬        
    list.sort(String.CASE_INSENSITIVE_ORDER);        
    System.out.println("대소문자 구분없이 오름차순 : " + list);// [a, A, B, C]                
    // 대소문자 구분없이 내림차순 정렬        
    list.sort(Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));        
    System.out.println("대소문자 구분없이 내림차순 : " + list); // [C, B, a, A]    
  }}

값이 측정 가능 한 int double 같은 경우 Comparator 클래스 안에서 정리

    public static void main(String[] args) {
        ArrayList<Integer> testBed = new ArrayList<>();

        for(int i=0;i<100; i++){
            testBed.add((int)((Math.random()*(1000-1+1))+1));            
        }
        //해당 ArrayList 배열 정렬 방법
        testBed.sort(Comparator.naturalOrder());
    }

정렬의 기준도 Comparable 을 통해 정렬 기준 설정 가능

public class SortArrayList {    
  public static void main(String[] args) {         
    // ArrayList 준비        
    ArrayList<Product> list = new ArrayList<>();        
    list.add(new Product("Galaxy", 2000));        
    list.add(new Product("Apple", 3000));        
    list.add(new Product("Shaomi", 1000));       
    System.out.println("원본 : " + list); 
    // price순 오름차순으로 정렬        
    Collections.sort(list);        
    System.out.println("오름차순 : " + list);     
    // price순 내림차순으로 정렬        
    Collections.sort(list, Collections.reverseOrder());        
    System.out.println("내림차순 : " + list);    
    }
}

class Product implements Comparable<Product> {
      
      private String name;    
      private int price;     
      
      //VO 개념
      public Product(String name, int price) {        
        this.name = name;        
        this.price = price;    
      }     
      
      @Override    
      public int compareTo(Product product) {        
        if (product.price < price) {            
          return 1;    // 가격 기준으로 상품의 가격 기준
        } 
        else if (product.price > price) {            
          return -1;   // 가격 역순 상품의 정렬
        }       
        return 0;    
      }    
      
      @Override    
      public String toString() {        
        return "[ " + this.name + ": " + this.price + " ]";    
      }
  }

정렬의 기준도 Comparator 을 통해 custom한 정령 기준 부여 가능

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator; 
public class SortArrayList {   
   public static void main(String[] args) {         
      // ArrayList 준비        
      ArrayList<Product> list = new ArrayList<>();        
      list.add(new Product("Galaxy", 2000));        
      list.add(new Product("Apple", 3000));        
      list.add(new Product("Shaomi", 1000));        
      System.out.println("원본 : " + list); 
      // price순 오름차순으로 정렬        
      Collections.sort(list, new ProductPriceComparator());        
      System.out.println("price 순 오름차순 : " + list); 
      // price순 내림차순으로 정렬        
      Collections.sort(list, new ProductPriceComparator().reversed());        
      System.out.println("price 순 내림차순 : " + list); 
      // name순 오름차순으로 정렬        
      Collections.sort(list, new ProductNameComparator());        
      System.out.println("price 순 오름차순 : " + list); 
      // name순 내림차순으로 정렬        
      Collections.sort(list, new ProductNameComparator().reversed());        
      System.out.println("price 순 내림차순 : " + list);
    }

    //가격 순 정렬
    private static class ProductPriceComparator implements Comparator<Product>{

        @Override
        public int compare(Product o1, Product o2) {
            if(o1.price > o2.price){
                return 1;
            }
            else if(o1.price < o2.price){
                return -1;
            }
            return 0;
        }
    }

    //이름 순 정렬
    private static class ProductNameComparator implements Comparator<Product>{

        @Override
        public int compare(Product o1, Product o2) {
            return o1.name.compareTo(o2.name);
        }
    }
    //Product는 생략...
}

※ 알고리즘 공부의 방향성 찾기

1. 다음 부터는 공부 할때 항상 노트랑 팬을 들고 공부를 하자.
2. 10분 고민 뒤 바로 생각안나면 찾아보자 (나는 쌓여 있는게 없다. 시간도 부족하다.)
3. 근데 아무리 생각해 봐도 이 책은 수준이 좀 높은게 아닐까 싶다. 일단 지금 이 파트는 너무 어렵다. 일단 급한 정렬 알고리즘 부터 본다. 복잡한 수식은 일단 재껴 놓는게 필요
4. 이 책 문제점이 알고리즘 연습문제에 대한 풀이가 없다. 연습문제는 주말에 몰아서 풀어야 할듯 진도 위주 진행. part2완료.