[이코테 2021 강의] 1. 알고리즘 성능평가 (자바 코드 예시)

본 게시글은 나동빈 님의 "이것이 취업을 위한 코딩 테스트다 with 파이썬"의 유투브 강의인 이코테 2021 강의를 듣고 정리한 정리본입니다.

 

(이코테 2021 강의 몰아보기) 1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기 

해당 영상의 " 알고리즘 성능 평가" 부분만을 정리한 게시글입니다.

 

복잡도(Complexity)

• 복잡도는 알고리즘의 성능을 나타내는 척도
  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
    • 시간 복잡도가 높다 → 더 많은 수행시간이 소요
    • 시간 복잡도가 낮다 → 해당 알고리즘이 더 빨리 실행
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
    • 공간 복잡도가 높다 → 많은 메모리가 필요하다.
    • 공간 복잡도가 낮다 → 더 적은 메모리가 필요하다.
• 동일한 기능을 수행하는 알고리즘? → 복잡도가 낮을수록 좋은 알고리즘

 

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
  • 함수의 상한만을 나타냄
    • 상한: 최악의 경우를 나타냄. 즉 ~보다 늦지 않다는 뜻
• ex) 연산 횟수가 3N³ + 5N² + 1,000,000인 알고리즘
  • 빅오 표기법: O(N³)이라고 나타냄
    • 빅오 표기법은 차수가 가장 큰 항만 남김(가장 빠르게 증가하는 항만을 고려)
  • ex) N이 100,000,000(1억)이라고 가정했을 때
    • 3N³의 값이 엄청나게 커지기 때문에 5N² + 1,000,000의 값은 3N³에 비해서 상대적으로 작은 수가 됨
    • N이 굉장히 큰 값이 될 수 있다고 가정했을 경우 → 이 함수의 N³만을 고려한다고 해도 충분히 가늠해 볼 수 있음.
• 알고리즘은 상수 시간, 로그 시간, 선형 시간 등으로 표기법을 붙여 해당 알고리즘의 성능을 나타낼 수 있음

상수 시간: 상수 번(몇 번)의 연산만 거치면 수행이 완료되는 경우

로그 시간: logN에 비례하는 만큼 수행

선형 시간: 데이터의 크기가 N일 경우 N에 비례하여 수행이 완료됨

 

 

시간 복잡도 계산해보기 1

• N개의 데이터 합을 구하는 프로그램

public class Example {
    public static void main(String[] args) {
        int[] array = {3,5,1,2,4}; // 5개의 데이터(N = 5)

        int summary = 0; // 합계를 저장할 변수

        // 모든 데이터를 하나씩 확인하며 합계를 계산
        for(int i : array){
            summary += i;
        }

        // 결과 출력
        System.out.println(summary);
    }
}

• 모든 데이터를 하나씩 확인하며 합계를 계산 → 수행 시간은 데이터의 개수 N에 비례
  • 시간 복잡도: O(N)

 

시간 복잡도 계산해보기 2

• 2중 반복문을 이용하는 프로그램

public class Example {
    public static void main(String[] args) {
        int[] array = {3,5,1,2,4}; // 5개의 데이터(N = 5)

        for(int i : array){
            for(int j : array){
                int temp = i * j;
                System.out.println(temp);
            }
        }

    }
}

• 시간 복잡도: O(N²)
• 모든 2중 반복문의 시간 복잡도가 O(N²)인 것은 아님
  • 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 함.

 

요구사항에 따라 적절한 알고리즘 설계하기

• 시간제한(수행시간 요구사항)이 1초일 경우(파이썬 기준)
  • N의 범위가 500: 시간 복잡도가 O(N³)인 알고리즘 설계
  • N의 범위가 2,000: 시간 복잡도가 O(N²)인 알고리즘 설계
  • N의 범위가 100,000: 시간 복잡도가 O(NlogN)인 알고리즘 설계
  • N의 범위가 10,000,000: 시간 복잡도가 O(N)인 알고리즘 설계

 

수행 시간 측정 소스코드 예제

public class Example {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis(); // 측정 시작
        
        // ~ 프로그램 소스코드 ~
        
        long endTime = System.currentTimeMillis(); // 측정 종료
        System.out.println("time = " + (endTime - startTime)); // 수행 시간 출력

    }
}