한국어
메뉴

자료 구조와 알고리즘

시간 복잡도가 O(n²)인 프로그램에서 데이터 수가 1,000일 때 처리 시간이 0.5초였다. 데이터 수를 4,000으로 하면 처리 시간은 약 몇 초가 되는가?

  1. A2초
  2. B8초
  3. C32초
정답과 해설 보기

정답: B. 8초

O(n²)에서는 처리 시간이 데이터 수의 제곱에 비례하므로, 데이터 수가 4배가 되면 처리 시간은 4² = 16배가 되어 0.5초 × 16 = 8초입니다. 2초는 데이터 수에 비례하는 O(n)의 경우, 32초는 세제곱에 비례하는 O(n³)의 경우(4³ = 64배)의 값입니다. 실제로는 데이터가 캐시에 다 들어가지 않게 되는 등의 영향으로 이보다 느려지기도 합니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을 찾는다. 목표 값은 반드시 배열 안에 있고 어느 위치에 있을 확률도 같을 때, 비교 횟수의 평균은 얼마인가?
  2. 배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?
  3. 빈 스택에 대해 push 1, push 2, pop, push 3, push 4, pop, pop의 순서로 조작했다. pop으로 꺼낸 값을 차례로 나열한 것은?
  4. 빈 큐에 A, B, C의 순서로 원소를 넣고 하나를 꺼낸 뒤, D를 넣고 하나를 꺼내고, E를 넣고 하나를 꺼냈다. 꺼낸 원소를 차례로 나열한 것은?
  5. 역폴란드 표기법(후위 표기법)으로 쓴 식 '3 4 + 2 * 5 −'를, 수가 오면 스택에 쌓고 연산자가 오면 두 값을 꺼내 계산하여 결과를 쌓는 방법으로 평가했다. 결과는 얼마인가? 여기서 연산자의 왼쪽 값은 먼저 쌓인 쪽의 값으로 한다.