그래프는 한 번의 순회 n회, 이중 반복 n²회, 정렬된 배열의 이진 탐색 최악 비교 floor(log₂n)+1회를 비교하는 모형입니다. Big-O는 실행 시간의 초 단위 값이나 모든 입력에서의 우열을 뜻하지 않습니다. 작은 입력·상수·구현 환경도 실제 속도에 영향을 줍니다.
공간복잡도
원리와 활용
입력이 커질 때 추가 메모리가 얼마나 필요한지 봅니다.
활용 복사·재귀·제자리 처리 비교
공간복잡도는 입력 크기에 따라 필요한 메모리가 어떻게 늘어나는지 봅니다. 여기서는 입력을 제외한 보조 공간을 셉니다.
↔ 드래그하여 이동
자세히 알아보기
보조 공간은 입력 저장소와 구분해 셉니다. 그림은 원소 한 개 또는 변수 한 개를 한 칸으로 세는 모형이며 실제 바이트 크기는 구현에 따라 다릅니다. 배열 복사와 재귀 호출 스택도 포함하고, 결과 공간의 포함 여부를 명시해야 합니다.