기타
시간복잡도(Big-O 표기법)에 관하여
crazydeer
2022. 7. 2. 16:32
반응형
정의
- 컴퓨터(하드웨어) 마다 알고리즘의 속도는 다르기 때문에 "완료까지 걸리는 절차의 수"로 결정된다.
예시
1. Linear Search
: 데이터를 검색할때 하나씩 검색한다. 따라서 입력의 사이즈가 N이라고 한다면 한번 다 검색하려면 N번 검색해야한다. 이를 O(N) 이라고 한다.
2. O(1)
| def print_first(arr): print(arr[0]) |
> "arr라는 배열에서 첫번째 element를 출력해라"
> 입력되는 배열의 사이즈가 10이든 100이든 단 1번의 스텝만 필요하다.
> 이런 경우를 시간 복잡도로 O(1) 이라고 한다.
3. 또 다른 O(1)
| def print_first(arr): print(arr[0]) print(arr[0]) |
> 2번의 Step이 필요. 그렇다고 O(2)라고 하느냐 아니다.
> 큰 원리에만 관심이 있기 때문에 미리 정해진 숫자에 따라 작동한다.
> 따라서 이 또한 O(1) 이라고 표현한다.
- 위 두가지 경우를 인풋의 사이즈가 어떻든간에 Constant Time (일정한 시간/상수)로 동작하기 때문에 가능만 하다면 선호되어야할 형태다. 근데 현실은 이렇게 알고리즘이 나오기는 쉽지 않음
4. O(n)
| def print_all(arr): for n in arr: print(n) |
> O(N)
5. O(n^2)
| def print_twice(arr): for n in arr: for x in arr: print(x, n) |
> O(N^2) : 중첩 루프
6. O(log n)
- 이진검색 알고리즘과 같은 경우에서 나오는 로그 시간 복잡도
절반을 나눠서 검색하기 때문에 데이터 사이즈가 2배가 되어도 스텝은 1만 증가함
대신! 정렬되지 않은 배열에는 사용할 수 없다.
> O(log N)
비교 그래프
- 가장 선호되는 건 O(1) 상수 시간: 인풋이 늘어나도 변하지 않음
- 그 다음은 O(log N), O(N), O(N^2) 순으로 효율적이다.
참고
반응형