O(1)
반복 없음
배열 인덱스 접근처럼 입력 크기와 상관없이 한 번 처리한다.
Big-O Reading
반복문 구조를 보면 시간 복잡도 후보가 빠르게 좁혀진다
시험에서는 정확한 초 단위가 아니라 입력 크기 n이 커질 때 실행 횟수가 어떻게 커지는지를 묻는다.
O(log n)
절반씩 감소
이진 탐색처럼 검사 범위가 매번 크게 줄어든다.
O(n)
한 줄 반복
배열 전체 순회처럼 n개를 한 번씩 본다.
O(n log n)
분할과 순회
병합 정렬처럼 나누면서 각 단계에서 전체를 처리한다.
O(n²)
중첩 반복
이중 for문처럼 각 원소마다 다시 n개를 비교한다.