Java-자료구조 (시간 복잡도)

알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
• Ω (오메가) 표기법: Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• Θ (세타) 표기법: Θ(N)
  • 세타 표기법은 알고리즘 평균 실행 시간을 표기

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O표기법을 중심으로 익히면 됨

3. 대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(log n), O(n), O(nlog n), O(n^2), O(2^n), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)
      • 참고: log n 의 베이스는 2 - log_2 n
• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
  • 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.
  • n이 1이든 100이든, 1000이든, 10000이든 실행을
    • 무조건 2회(상수회) 실행한다: O(1)
    • if (n > 10) { System.out.println(n); }
    • n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)
      • 다음 코드는 이중 반복문이지만, 상위는 상수로 반복하므로, 3n 실행
      • for (int num = 0; num < 3; num++) { for (int index = 0; index < n; index++) { System.out.println(index) } }
    • n에 따라, n^2번, n^2 + 1000 번, 100n^2 - 100, 또는 300$n^2 + 1번등 실행한다: O(n^2$)
      • 다음 코드는 삼중 반복문이지만, 상위는 상수로 반복하므로, 3n^2 실행
      • for (int i = 0; i < 3; i++) { for (int num = 0; num < n; num++) { for (int index = 0; index < n; index++) { System.out.println(index) } } }

4.1 알고리즘1: 1부터 n까지의 합을 구하는 알고리즘1

• 합을 기록할 변수를 만들고 0을 저장
• n을 1부터 1씩 증가하면서 반복
• 반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함
• 반복이 끝나면 합을 출력

public class Main {
    public int sum(int n) {
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total += i;
        }
        return total;
    }
}

main mainObject = new Main();
mainObject.sum(10);
// 55

시간 복잡도 구하기

• 1부터 n까지의 합을 구하는 알고리즘1
  • 입력 n에 따라 덧셈을 n 번 해야 함 (반복문!)
  • 시간 복잡도: n, 빅 오 표기법으로는 O(n)

public class Main {
    public int sum(int n) {
        return n * (n + 1) / 2;
    }
}

Main mainObject = new Main();
mainObject.sum(10);
// 55

시간 복잡도 구하기

• 1부터 n까지의 합을 구하는 알고리즘2
  • 입력 n이 어떻든 간에, 곱셈/덧셈/나눗셈 하면 됨 (반복문이 없음!)
  • 시간 복잡도: 1, 빅 오 표기법으로는 O(1)

4.3 어느 알고리즘이 성능이 좋은가요?

• 알고리즘1 vs 알고리즘2
  • O(n) vs O(1)

이와 같이, 동일한 문제를 푸는 알고리즘은 다양할 수 있음
어느 알고리즘이 보다 좋은지를 객관적으로 비교하기 위해, 빅 오 표기법등의 시간복잡도 계산법을 사용함

자료구조, 알고리즘부터는 빅 오 표기법으로 성능을 계산 해보며, 이에 익숙해 져야 한다.