프로그래밍 문제를 해결하는 데에는 여러가지 방법이 있다. 어떤 방법이 다른 방법보다 나은지(어떤 방법을 선택할지) 어떻게 알 수 있을까?
알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 시간복잡도(Time complexity)라고 하고 주로 빅오표기법(Big O notation)을 이용해 나타낸다. 입력값이 n개 일 때 걸리는 시간을 비교해 알고리즘의 효율성을 표현하기 위한 방식이다. 이 때 n의 값은 충분히 크다고 가정한다.
n의 값에 따른 알고리즘의 시간복잡도는 다음과 같다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
이해를 돕기 위해 예시를 보자. 다음 코드는 크기가 n인 정수배열에서 0보다 작은 값이 있으면 true, 없으면 false를 반환한다. 시간복잡도를 계산해보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public boolean hasNegativeNumber(int array[]){ if(array==null){ return false; } for(int i=0 ; i<array.length ; i++){ if(array[i]<0){ return true; } } return false; } | cs |
배열을 순서대로 탐색하므로 만약 array[0]의 값이 음수라면 시작하자마자 결과가 나오겠지만(best case) 음수가 배열의 맨 마지막에 있다면array[n]까지 탐색해야하므로(worst case) n만큼의 시간이 걸린다. 하지만 아무리 최악의 경우라도 O(n)보다 시간이 더 걸리지는 않는다. 위의 코드의 시간복잡도는 O(n)이다.
두번째로는 정수배열과 목표값을 입력으로 받아 배열 요소의 값의 합이 목표값과 일치하는 인덱스를 찾아 반환하는 코드를 보자.
1 2 3 4 5 6 7 8 9 10 | public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[] { i, j }; } } } throw new IllegalArgumentException("No two sum solution"); } | cs |
이중 for문을 사용하므로 최대 n(n-1)/2만큼의 시간이 걸린다. 우리는 n이 충분히 큰 수라고 가정하기 때문에 가장 큰 항에서 상수는 무시하고 따라서 이 경우 시간복잡도는 O(n²)이다.
Big O notation은 실행시간이 꼭 그만큼 걸린다기 보다는 실행시간의 최댓값은 이정도이기때문에 '아무리 최악의 케이스여도 이정도 속도까지는 보장한다'라고 이해하면 된다.
'코딩문제(LeetCode) > Easy' 카테고리의 다른 글
| 비트연산자란? (0) | 2019.03.16 |
|---|---|
| [코딩연습] Search Insert Position 숫자를 넣을 자리 찾기 (0) | 2019.03.14 |
| [코딩연습] Length of Last Word 마지막 단어의 길이 구하기 (2) | 2019.03.12 |
| [코딩연습] Plus One 배열을 정수로 보고 1 더하기 (0) | 2019.03.11 |
| [코딩테스트연습사이트] LeetCode (1) | 2019.02.24 |
