한국어
메뉴

자료 구조와 알고리즘

원소 수가 n인 배열에서 서로 다른 두 원소의 쌍을 모두 한 번씩 비교하는 처리(i번째 원소를 그보다 뒤에 있는 모든 원소와 비교하는 것을, i를 하나씩 늘려 가며 반복하는 이중 루프)의 시간 복잡도는?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
정답과 해설 보기

정답: C. O(n²)

비교하는 쌍의 수는 (n−1) + (n−2) + … + 1 = n(n−1)/2이며, n = 10이면 45회, n = 1000이면 499,500회입니다. 시간 복잡도의 차수는 n이 커졌을 때의 증가 방식만 보므로, 계수 1/2이나 낮은 차수의 항을 생략하여 O(n²)으로 나타냅니다. n이 2배가 되면 횟수는 약 4배가 됩니다. O(n)은 모든 원소를 한 번씩 보기만 하는 처리, O(n log n)은 병합 정렬처럼 절반으로 나누기를 반복하는 처리의 시간 복잡도입니다.

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

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

  1. 시간 복잡도가 O(n²)인 프로그램에서 데이터 수가 1,000일 때 처리 시간이 0.5초였다. 데이터 수를 4,000으로 하면 처리 시간은 약 몇 초가 되는가?
  2. 서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을 찾는다. 목표 값은 반드시 배열 안에 있고 어느 위치에 있을 확률도 같을 때, 비교 횟수의 평균은 얼마인가?
  3. 배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?
  4. 빈 스택에 대해 push 1, push 2, pop, push 3, push 4, pop, pop의 순서로 조작했다. pop으로 꺼낸 값을 차례로 나열한 것은?
  5. 빈 큐에 A, B, C의 순서로 원소를 넣고 하나를 꺼낸 뒤, D를 넣고 하나를 꺼내고, E를 넣고 하나를 꺼냈다. 꺼낸 원소를 차례로 나열한 것은?