알고리즘의 복잡도란? (3. 빅오 표기법)
1. 공간 복잡도 (Space complexity)
2. 시간 복잡도 (Time complexity)
3. 빅오 표기법 (Big-O notation)
복잡도를 표현하는 단위입니다.
거리의 단위에 km 가 있고, 무게의 단위에 kg 이 있듯
복잡도의 단위로는 O 가 있습니다.
공간 복잡도와 시간 복잡도 둘 다에 사용되며
최악의 경우를 가정하여 나타냅니다.
최악이 무슨 말인지 아래 예시를 보여드리겠습니다.
1 2 3 4 5 6 7 8 9 | public boolean contains(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { if (arr[i] == num) { return true; } } return false; } | cs |
위 함수의 경우, 운이 좋으면 한번만에 찾아서 return true가 될 수도 있고,
운이 최악이면 arr 전체를 다 뒤져야할수도 있습니다.
Big-O 는 이 최악을 가정하여 나타내므로
O(n) 이 위 함수의 시간 복잡도입니다.
n 은 뭐냐면 입력받은 배열의 길이를 뜻합니다.
또 특이한 점은 상수는 간소화한다는 것입니다.
O(k * 1) => O(1)
O(k * n) => O(n)
O(n + k) => O(n)
O(k * n제곱) => O(n제곱)
아래 함수를 예로 들겠습니다. (함수 내용 이해할 필요 없음)
시간 복잡도는 "2n + 2" 이지만 (n + n + 2)
Big-O 표기법으로는 O(n) 입니다.
공간 복잡도는 "n + 3" 이지만 (checked, i => n + 2 + 1)
Big-O 표기법으로는 O(n) 입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public int solution(int[] A) { boolean[] checked = new boolean[A.length + 2]; for (int i = 0; i < A.length; i++) { checked[A[i]] = true; } for (int i = 1; i < checked.length; i++) { if (!checked[i]) { return i; } } return -1; } | cs |
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| codility - Fish 정답 및 해설 (0) | 2017.08.08 |
|---|---|
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
| 알고리즘의 복잡도란? (2. 시간 복잡도) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (1. 공간 복잡도) (0) | 2017.07.28 |
| codility - Triangle 정답 및 해설 (0) | 2017.07.12 |
알고리즘의 복잡도란? (2. 시간 복잡도)
1. 공간 복잡도 (Space complexity)
2. 시간 복잡도 (Time complexity)
반복문을 총 몇번 도는지를 의미합니다.
아래는 1부터 n까지의 합을 구하는 함수입니다.
시간 복잡도는 "n" 입니다.
1 2 3 4 5 6 7 8 9 | public int solution(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += i; } return sum; } | cs |
같은 함수를 수학공식을 이용해 아래와 같이 바꾸면 시간 복잡도는 "1" 이 됩니다.
(수학을 잘하면 알고리즘에 유리합니다)
1 2 3 | public int solution(int n) { return (1 + n) * n / 2; } | cs |
API 사용시에는 주의해야합니다.
아래 함수의 시간 복잡도는 얼마일까요? "A.length" 일까요?
(함수 내용은 이해할 필요 없음)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public int solution(int[] A) { List<Integer> marks = new ArrayList<>(); for (int i = 0; i < A.length; i++) { if (A[i] > A.length) { return 0; } if (marks.contains(A[i])) { return 0; } marks.add(A[i]); } return 1; } | cs |
답은 "A.length X A.length" 입니다. "A.length" 의 제곱이지요.
왜냐하면 ArrayList.contains() 함수의 시간 복잡도가 "해당 list의 길이" 이기 때문입니다.
(내부적으로 list 전체를 반복문을 돌면서 인자로 던져준 객체가 있는지 확인합니다)
위 함수에서 ArrayList 대신 HashSet 을 사용하면 어떨까요?
출력은 같지만 복잡도는 "A.length" 가 됩니다.
HashSet.contains() 함수의 시간 복잡도는 "1" 이기 때문입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public int solution(int[] A) { Set<Integer> marks = new HashSet<>(); for (int i = 0; i < A.length; i++) { if (A[i] > A.length) { return 0; } if (marks.contains(A[i])) { return 0; } marks.add(A[i]); } return 1; } | cs |
3. 빅오 표기법 (Big-O notation)
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| codility - Brackets 정답 및 해설 (0) | 2017.08.08 |
|---|---|
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
| 알고리즘의 복잡도란? (1. 공간 복잡도) (0) | 2017.07.28 |
| codility - Triangle 정답 및 해설 (0) | 2017.07.12 |
| codility - MaxProductOfThree 정답 및 해설 (0) | 2017.07.12 |
알고리즘의 복잡도란? (1. 공간 복잡도)
복잡도가 낮을 수록 성능이 뛰어난 알고리즘입니다.
알고리즘의 복잡도(Complexity)는 두 가지 요소로 측정합니다.
1. 공간 복잡도 (Space complexity)
간단합니다. 사용되는 변수의 개수를 의미합니다.
단, 인자 변수들은 일반적으로 제외하고 카운트합니다.
예를들어 아래와 같은 함수의 경우, 공간 복잡도는 "2" 입니다. (sum, i)
(함수 내용은 이해할 필요 없음)
1 2 3 4 5 6 7 8 9 | public int solution(int n) { int sum = 0; for (int i = 1; i <= n; i++) { sum += i; } return sum; } | cs |
또 하나의 예시를 들어보면, 아래 함수의 경우 공간 복잡도는 "N + 3" 입니다. (counter, tmpMaxCounter, doneMaxCounter, i)
(마찬가지로 함수 내용은 이해할 필요 없음)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | public int[] solution(int N, int[] A) { int[] counter = new int[N]; int tmpMaxCounter = 0; int doneMaxCounter = 0; for (int i = 0; i < A.length; i++) { if (A[i] > N) { doneMaxCounter = tmpMaxCounter; } else { if (counter[A[i] - 1] < doneMaxCounter) { counter[A[i] - 1] = doneMaxCounter; } counter[A[i] - 1]++; if (counter[A[i] - 1] > tmpMaxCounter) { tmpMaxCounter = counter[A[i] - 1]; } } } if (doneMaxCounter > 0) { for (int i = 0; i < counter.length; i++) { if (counter[i] < doneMaxCounter) { counter[i] = doneMaxCounter; } } } return counter; } | cs |
2. 시간 복잡도 (Time complexity)
3. 빅오 표기법 (Big-O notation)
'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글
| 알고리즘의 복잡도란? (3. 빅오 표기법) (0) | 2017.07.28 |
|---|---|
| 알고리즘의 복잡도란? (2. 시간 복잡도) (0) | 2017.07.28 |
| codility - Triangle 정답 및 해설 (0) | 2017.07.12 |
| codility - MaxProductOfThree 정답 및 해설 (0) | 2017.07.12 |
| codility - Distinct 정답 및 해설 (0) | 2017.07.12 |
