#시간복잡도
- 시간복잡도란?
- 알고리즘문제를 풀다보면 등장하는 효율성 테스트가 있다. 정확성 테스트를 통과하더라도 효율성테스트에서 떨어지는 경우가 많다. 효율성 테스트를 실패하면 '시간 초과'라는 메시지가 나온다.
효율적인 알고리즘은 시간 복잡도가 낮은 코드를 말하는 것이다. - 시간복잡도란 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수와 소요 시간의 비례도를 말한다.
시간복잡도를 효율화한 코드는 이 비례도를 최소화한 코드를 말하는 것이다.
- Big-O 표기법
- 시간 복잡도를 표기하는 방법은 여러 가지가 있는데, Big-O 표기법이 가장 많이 사용된다.
- Big-O 표기법은 최악의 경우를 고려하는 표기법이다.
이를 사용하는 이유는 프로그램의 실행 중 여러 연산값을 도출하는 데 걸리는 최악의 경우의 시간을 고려 할 수 있기 때문이다.
예를 들어 어떤 프로그램이 값을 도출해내는 데 소요되는 시간의 범위가 1~100초 사이이고 100개의 값을 연산해야 한다면 Big-O표기법은 최악의 경우를 고려하여 100*100인 10000초로 계산한다. 개발자는 이를 염두에 두고 효율적인 코드를 구성하기 위한 프로그래밍을 할 수 있을 것이다.
- Big-O 표기법의 종류
- O(1)
▪ O(1)은 constant complexity라고 불림.
▪ 입력값이 증가하더라도 시간이 늘어나지 않음.
▪ 즉시 출력값을 얻어낼 수 있음.
▪ O(1)의 시간복잡도를 가지는 알고리즘의 예시는 다음과 같다.
public int O_1_algorithm(int[] arr, int idx) { return arr[idx]; } String[] arr1 = new String[]{"hello", "new", "world"} int[] arr2 = new int[]{1,2,3}; ind idx = 0; String answer = O_1_algorithm(int[] arr, int idx); System.out.println(answer); // hello
- O(n)
▪ O(n)은 linear complexity라고 불림
▪ 입력값과 시간이 같은 비율로 늘어남(1개/1초 -> 100개/100초)
▪ O(n)의 시간복잡도를 가지는 알고리즘의 예시는 다음과 같다.
public void O_n_algorithm(int n) { for(int i = 0; i < n; i++) { System.out.println(i); } }
- O(log n)
▪ O(log n)은 logarithmic complexity라고 불림
▪ Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
▪ 대표적인 알고리즘으로 BST(Binary Search Tree)가 있음 - O(n^2)
▪ O(n^2)은 quadratic complexity라고 불림
▪ 입력값의 제곱의 비율로 시간이 늘어남
▪ n의 값과 상관없이 표기법은 같다.
▪ O(n^2)의 시간복잡도를 가지는 알고리즘의 예시는 다음과 같다.
public void O_quadratic_algorithm(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println(a); } } } public void another_O_quadratic_algorithm(int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { System.out.println(1); } for(int k = 0; k < n; k++) { System.out.println(1); } for(int l = 0; l < n; l++) { System.out.println(1); } } }
- O(2^n)
▪ O(2^n)은 exponetial complexity라고 불림
▪ Big-O 표기접 중 가장 느린 시간복잡도를 가진다. ▪ 피보나치 수 알고리즘이 이 시간복잡도를 가짐
public int fibonacci(int n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n-2);
}
'개발지 > Today I learn' 카테고리의 다른 글
[1208] 자바 스프링 - Spring Framework (3) | 2023.12.08 |
---|---|
[1205] 자바 - 알고리즘(탐욕 알고리즘, BFA, BSA) (2) | 2023.12.05 |
[1128] 자바 - Tree traversal(트리 순회) (1) | 2023.11.28 |
[1128] 자바 - Graph (그래프) (2) | 2023.11.28 |
[1127] 자바 - Graph Traversal(그래프 탐색) (4) | 2023.11.27 |