무엇을 세는가
배열을 처음부터 끝까지 한 번 읽으면 원소 수에 비례하는 작업이 필요하다. 반면 모든 서로 다른 두 원소 쌍을 검사하면 n(n−1)/2쌍을 다룬다. 두 방식은 입력이 커질 때 비용의 증가 양상이 다르다.
입력 크기의 뜻
배열에서는 원소 수가 흔한 기준이지만 정수 문제에서는 숫자의 비트 수가 입력 길이일 수 있다. 수의 값 N과 그 값을 표현하는 자릿수는 같은 크기가 아니다. 복잡도를 읽을 때 n이 무엇인지 먼저 확인한다.
최악과 평균
선형 탐색은 첫 원소에서 찾으면 한 번만 비교해도 되지만 없거나 끝에 있으면 전체를 살핀다. 평균 비용은 입력이 어떤 확률로 주어진다고 가정하는지에 의존한다. 최악 비용과 평균 비용은 서로 바꾸어 쓰지 않는다.
실행 시간과의 관계
점근적 표기는 큰 입력에서 증가율을 비교하는 데 유용하다. 하지만 상수 비용, 메모리 접근, 실행 환경에 따라 작은 입력의 실제 속도는 달라질 수 있다. O(n)이라는 표현 자체가 특정 초 안에 끝난다는 보장은 아니다.
관련 문서
알고리즘 / 선형 탐색 / 이진 탐색 / 분할 정복 / 힙 정렬 / 분할 상환 분석 / 공간 복잡도 / 이진법