Big-O
수학에서 빅오란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 표기방법을 말합니다.
컴퓨터과학에서 빅오는 어떤 알고리즘을 수행하는 데 걸리는 시간 또는 공간 복잡도를 표기하는 방법입니다. 그렇다면 왜 컴퓨터과학에서 빅오 표기법이 필요할까요??
보통 일반 컴퓨터의 경우 1초에 억단위의 연산을 수행하기 때문에 작은 입력에 대해서는 효율적인 알고리즘과 비효율적인 알고리즘의 수행 시간의 차이를 확인하기 어렵습니다.
또한 그래프에서 볼 수 있듯이 작은 값에서는 빨리 동작하는 알고리즘도 충분히 큰 값에서는 매우 느리게 동작할 수도 있기 때문에 보통 알고리즘의 효율성을 나타내는 시간 복잡도를 표기하기 위해 빅오 표기법을 사용합니다.
시간복잡도
대부분의 알고리즘은 아래 시간 복잡도 중 하나에 속합니다.
상수 시간 | O(1) | 해시 테이블의 조회 및 삽입 연산 |
로그 시간 | O(logN) | 이진 탐색 |
선형 시간 | O(N) | 정렬되지 않은 배열에서 최소값 또는 최대값 탐색 |
선형 로그 시간 | O(N logN) | 병합 정렬, 퀵 정렬 |
2차 시간 | O(N^2) | 버블 정렬, 삽입 정렬 |
지수 시간 | O(C^N) | 재귀 문제 |
팩토리얼 시간 | O(N!) | 브루트포스를 이용한 외판원 문제 |
이러한 시간 복잡도들을 그래프로 나타내면 아래와 같으며, n이 커질수록 각 값들의 차이는 더욱 커지게 됩니다.
빅오 표기방법
1. 상수항은 무시한다. O(2N) → O(N)
2. 지배적이지 않은 항은 무시한다. O(N + 2) → O(N)
But M과 N 사이에 특별한 관계가 없는 경우 O(M + N)는 O(N)이나 O(M)으로 줄일 수 없습니다.
분할 상환 분석
ArrayList는 배열의 용량이 꽉 차게 되면 기존보다 크기가 2배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사하는 자료구조 입니다.
ArrayList에 원소를 삽입할 때 삽입할 용량이 남아있다면 삽입에 걸리는 시간 복잡도는 O(1)이지만, 용량이 부족한 경우 새로운 배열로 기존 원소를 복사해야 하므로 시간 복잡도는 O(N)이 되게 됩니다.
그렇다면 ArrayList에 원소를 삽입하는 연산의 시간 복잡도는 O(1)일까요? O(N)일까요??
답은 O(N)입니다!
ArrayList에서 크기를 늘리는 resize 작업은 어쩌다 한번 일어나는 작업입니다. 하지만 가끔 일어나는 resize 작업 때문에 삽입에 걸리는 전체 시간복잡도를 O(N)이라고 단정짓는 것은 지나치게 비관적이고 정확하지 않기 때문입니다.
이러한 이유때문에 등장한 개념이 바로 분할 상황 분석입니다.
즉, 최악의 경우는 가끔 발생하지만 한 번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용을 분할 상환한다는 개념입니다.
위의 ArrayList의 삽입 연산에 분할 상환을 적용해 알고리즘의 시간 복잡도를 계산하면 삽입에 걸리는 시간 복잡도는 O(1)이 되게 됩니다.
계산 과정을 보면 원소 N개를 삽입하는데 걸리는 시간은 O(3N)이 되고 원소 1개를 삽입한는 시간은 O(3), 즉 O(1)로 상수 시간을 갖게 됩니다.
'Python > Algorithm' 카테고리의 다른 글
다이나믹 프로그래밍 (DP) (0) | 2022.03.04 |
---|---|
투 포인터와 슬라이딩 윈도우 (0) | 2022.03.04 |
그래프 관련 알고리즘 (0) | 2022.03.01 |
버블 정렬, 선택 정렬, 삽입 정렬 (0) | 2022.03.01 |
트라이 (0) | 2022.02.27 |