성능을 초(sec)와 같은 절대적인 시간이 아닌, 입력 크기($n$)의 증가에 따른 연산 횟수의 증가율(상대적 성능)로 표현하는 방식이다. 하드웨어의 속도 차이를 배제하고 알고리즘 자체의 효율성을 평가할 때 사용한다.
1. 선형 시간 (Linear Time): $O(n)$
입력 크기($n$)가 증가함에 따라 처리 시간도 정비례하여 증가하는 경우다.
- 현실 예시: 영화 <기생충>의 피자 박스 접기.
- 하루 최대 생산량 = 100개
- 목표량 200개 $\rightarrow$ 2일 소요
- 목표량 $n$개 $\rightarrow$ $n/100$일 소요
- 특징: 물리적인 생산 시스템(도면 설계, 자동차 조립, 포장 기계 등)은 대부분 정직하게 $O(n)$을 따른다. 데이터 처리에서는
for문을 사용하여 리스트 전체를 1회 순회하는 탐색 등이 이에 해당한다.
2. 상수 시간 (Constant Time): $O(1)$
입력 크기($n$)가 아무리 커져도(1억 개든 1조 개든) 처리 시간이 변하지 않고 일정한 경우다.
- 기술 예시: 배열(Array)의 인덱스 접근 (Random Access).
- 배열은 메모리 상에 연속적으로 할당된다.
arr[i]에 접근하는 것은시작 주소 + (자료형 크기 $\times$ i)라는 단순 산술 연산 한 번으로 주소를 즉시 계산하여 찾아간다.- 따라서 첫 번째 원소(
arr[0])나 100만 번째 원소(arr[1000000])나 접근 속도는 물리적으로 동일하다.
3. 알고리즘별 성능 비교표 (일반적 위계)
“전문가다운 C++ 프로그램 디자인”에서 언급된 표는 자료구조와 알고리즘 선택에 따른 성능 차이를 보여준다. 효율성은 대략 다음 순서를 따른다.
| 표기법 | 명칭 | 설명 | 대표 알고리즘/자료구조 |
| $$O(1)$$ | 상수 시간 | 데이터 크기와 무관하게 즉시 완료 | 배열 인덱스 접근, 스택 Push/Pop, 해시 테이블 접근(평균) |
| $$O(\log n)$$ | 로그 시간 | 입력이 2배 늘어도 시간은 조금만 증가 | 이진 탐색 (Binary Search) |
| $$O(n)$$ | 선형 시간 | 입력과 시간이 1:1 비례 | 선형 탐색 (Linear Search), 일반적인 순회 |
| $$O(n \log n)$$ | 선형 로그 시간 | $$O(n)$$보다 조금 느림 | 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬 |
| $$O(n^2)$$ | 이차 시간 | 입력이 2배 늘면 시간은 4배 증가 | 이중 루프, 버블 정렬, 삽입 정렬 |
결론: 프로그래밍에서 성능 최적화란 결국 문제를 해결하는 로직을 $O(n^2)$에서 $O(n \log n)$으로, 혹은 $O(n)$에서 $O(\log n)$이나 $O(1)$로 낮출 수 있는 적절한 자료구조를 선택하는 과정이다.