상수 시간 O(1)
입력 크기와 상관없이 결과를 고정된(상수) 시간에 계산한다면 알고리즘이 상수 시간(constant time)에 실행된다고 합니다. 다음과 같은 경우입니다.
• 배열의 n번째 원소에 접근하기
• 스택에 넣고(push) 빼기(pop)
• 큐에 삽입하고(add) 삭제하기(remove)
• 해시 테이블의 원소에 접근하기
선형 시간 O(n)
알고리즘의 실행 시간이 입력 크기에 정비례하면 알고리즘이 선형 시간(linear time)에 실행된다고 합니다. 다음과 같은 경우입니다.
• 배열에서 원소 검색, 최솟값 찾기, 최댓값 찾기 등의 연산
• 연결 리스트에서 순회(traversal), 최솟값 찾기, 최댓값 찾기 등의 연산
Note ≡
자료 구조 내의 모든 노드를 방문한다면 시간 복잡도는 O(n)보다 같거나 큽니다.