기술 면접과 수업에서 자주 다루는 빅오 표기법, 대표적인 정렬 및 탐색 알고리즘, 재귀 패턴을 다룹니다.
카드 38장 · 기본 카드 · AI가 작성하고 두 번 검수했어요. 자유롭게 편집하세요.
- 빅오 표기법은 무엇을 측정하나요?
정답 보기
입력 크기가 커질 때 알고리즘의 실행 시간이나 공간 요구량이 어떻게 증가하는지를 나타냅니다.- O(1) 시간 복잡도를 정의하세요.
정답 보기
상수 시간입니다. 입력 크기와 관계없이 실행 시간이 변하지 않습니다.- O(n) 시간 복잡도를 정의하세요.
정답 보기
선형 시간입니다. 실행 시간이 입력 크기 n에 비례해 증가합니다.- O(log n) 시간 복잡도를 정의하세요.
정답 보기
로그 시간입니다. 실행 시간이 입력 크기의 로그에 따라 증가합니다.- O(n^2) 시간 복잡도를 정의하세요.
정답 보기
이차 시간입니다. 실행 시간이 입력 크기의 제곱에 따라 증가합니다.- O(n log n) 시간 복잡도를 정의하세요.
정답 보기
선형로그 시간입니다. 실행 시간이 n에 log n을 곱한 값입니다.- O(2^n) 시간 복잡도를 정의하세요.
정답 보기
지수 시간입니다. 입력 크기가 1 늘어날 때마다 실행 시간이 두 배가 됩니다.- 인덱스로 배열 요소에 접근하는 시간 복잡도는 얼마인가요?
정답 보기
O(1), 즉 상수 시간입니다.- 정렬되지 않은 배열에서 값을 찾는 시간 복잡도는 얼마인가요?
정답 보기
O(n), 즉 선형 시간입니다.- 정렬된 배열에서 이진 탐색의 시간 복잡도는 얼마인가요?
정답 보기
O(log n), 즉 로그 시간입니다.- 이진 탐색을 쓰려면 배열이 어떤 상태여야 하나요?
정답 보기
배열이 정렬되어 있어야 합니다.- 배열의 맨 앞에 요소를 삽입하는 시간 복잡도는 얼마인가요?
정답 보기
O(n), 즉 선형 시간입니다.- 여유 용량이 있는 동적 배열의 끝에 요소를 추가하는 시간 복잡도는 얼마인가요?
정답 보기
분할 상환 O(1), 즉 상수 시간입니다.- 해시 테이블 탐색의 평균 시간 복잡도는 얼마인가요?
정답 보기
좋은 해시 함수를 쓰면 O(1), 즉 상수 시간입니다.- 퀵 정렬의 평균적인 경우 시간 복잡도는 얼마인가요?
정답 보기
O(n log n), 즉 선형로그 시간입니다.
FlashKeepers