01.30 알고리즘

알고리즘에 대한 조건

• 알고리즘에 대한 조건
  • 입력 : 외부에서 제공되는 자료
  • 출력 : 적어도 2개 이상의 서로 다른 결과 출력
  • 명확성 : 수행과정은 무엇을 하기 위한 것인지 명확하게 정의
  • 유한성 : 알고리즘의 명령어 대로 수행했을 때 처리된 후 종료
  • 효율성 : 시-공간적 효율성을 가져야 하며 명백하게 실행가능

 

좋은 알고리즘이란?

• 문제를 정확히 해결해야 합니다.
  • 알고리즘의 가장 중요한 역할은 문제를 정확히 해결하는 것입니다.
• 빠르게 처리해야 합니다.
  
  • 신속, 정확! 어떤 일이든 빠르고 정확하게 해결한다는 건 그만큼 시간이라는 자원을 아낄 수 있다는 뜻이며, 같은 연산도 더 빠르게 수행할 수 있게 해준다면 아주 좋은 알고리즘입니다.
• 최소의 자원으로 최대의 효율을 내야합니다.
  • 문제 해결이라는 목적에 필요한 기능만 수행하면서 불필요한 자원(컴퓨터의 메모리 공간 또는 연산 시간)을 낭비하지 않는 게 좋은 알고리즘입니다.
• 단순 명료해야 합니다. 
  • 누구나 문제를 해결하는 과정을 보는 것만으로 쉽게 이해할 수 있어야 이 알고리즘이 어떤 문제를 어떻게 해결하는지 금세 파악할 수 있으며, 또 문제가 생겼을 때 수정하거나 보완할 수 있기 때문입니다.

시간 복잡도

• 알고리즘이 특정 크기 입력에 대한 수행 시간을 의미
• 알고리즘이 수행하는 필요 연산 횟수

정렬 알고리즘	시간 복잡도
Bubble Sort (버블 정렬)	O(n^2)
Selection Sort (선택 정렬)	O(n^2)
Insertion Sort (삽입 정렬)	O(n^2)
Quick Sort (퀵 정렬)	평균 : O(nlogn) / 최악 : O(n^2)
Merge Sort (병합 정렬)	O(nlogn)
Radix Sort (기수 정렬)	O(kn) / k : 최대 데이터의 자릿수
Arrays.sort()	평균 : O(nlogn) / 최악 : O(n^2)
Collections.sort()	O(nlong)

공간 복잡도

• 공간 복잡도를 표기할 때도 빅오 표기법을 이용합니다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시됩니다.
• 코딩 테스트에서 보통 메모리 사용량은 128~512MB 정도로 제한하며, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘지 않도록 알고리즘을 설계해야 합니다.

수행 시간 측정 코드

/////////////////////		시간차이(밀리세컨즈) : 58		/////////////////////

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        int []arr = new int [100_000_000];

        for(int i=0; i<100_000_000; i++) {
            arr[i] = (int) Math.random();
        }

        long before = System.currentTimeMillis(); //코드 실행 전 시간

        //실행할 소스코드
        Arrays.sort(arr);

        long after = System.currentTimeMillis(); // 코드 실행 후 시간
        long diff = (after - before); //두 시간에 차이
        System.out.println("시간차이(밀리세컨즈) : "+diff);

    }
}

/////////////////		Used Memory(MB) : 511		////////////////////

public class Main {

    public static void main(String[] args) {

        int []arr = new int [100_000_000];

        for(int i=0; i<100_000_000; i++) {
            arr[i] = (int) Math.random();
        }

        // Garbage Collection으로 메모리 초기화
        System.gc();


        // 실행전 메모리 사용량 조회
        long before = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        System.out.println("Used Memory : " + before);


        // 프로그램 소스코드
        Arrays.sort(arr);

        // Garbage Collection으로 메모리 정리
        System.gc();

        // 실행 후 메모리 사용량 조회
        long after  = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();

        // 메모리 사용량 측정
        long usedMemory = (before - after)/1024;

        System.out.println("Used Memory(MB): " + usedMemory);

    }
}