예를 들어 배열 전체의 크기가 8일 때 선택 정렬이 어떻게 이루어질지 생각해봅시다. 첫 번째 indexOfMinimum 호출에서는 배열의 모든 값을 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 8번 실행됩니다. 윗부분에서, 첫번째 indexOfMinimum 호출을 했을때, 8번 반복이 된다는것이 이해가 가질않습니다. indexOfMinimum의 반복문에서 배열의 첫번째 인덱스와 (두번째, 세번째, ..., 여덟번째 인덱스)와 각각 비교를 하면 반복문이 7번 실행되는거아닌가요? for(var i = minIndex+1; i < array.length; i++) { if(array[i] < minValue) { minIndex = i; minValue = array[i]; } }

Q: 예를 들어 배열 전체의 크기가 8일 때 선택 정렬이 어떻게 이루어질지 생각해봅시다. 첫 번째 indexOfMinimum 호출에서는 배열의 모든 값을 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 8번 실행됩니다. 윗부분에서, 첫번째 indexOfMinimum 호출을 했을때, 8번 반복이 된다는것이 이해가 가질않습니다. indexOfMinimum의 반복문에서 배열의 첫번째 인덱스와 (두번째, 세번째, ..., 여덟번째 인덱스)와 각각 비교를 하면 반복문이 7번 실행되는거아닌가요? for(var i = minIndex+1; i < array.length; i++) { if(array[i] < minValue) { minIndex = i; minValue = array[i]; } }

indexOfMinimum 함수에는 for 문을 시작하기 전에 startindex 에 해당하는 값을 저장하는 부분 때문에 8번이라고 하는거 같습니다. var minValue = array[startIndex]; var minIndex = startIndex;

주요 내용

코스: 컴퓨터과학 > 단원 1

단원 4: 선택 정렬

선택 정렬 분석하기

구글 클래스룸

선택 정렬은 배열의 인덱스를 반복합니다. 각 인덱스마다 indexOfMinimum과 swap을 호출합니다. 배열의 길이가

n

이라면 배열에는 요소가

n

개 있습니다.

선택 정렬은 반복문을 실행할 때마다 코드 두 줄을 실행하므로 총

2 n

줄의 코드를 실행한다고 생각할 수 있습니다. 하지만 사실은 다릅니다! indexOfMinimum 과 swap은 함수입니다. 함수가 호출된다는 것은 여러 줄의 코드가 실행되는 것입니다.

swap을 한 번 호출할 때마다 몇 줄의 코드가 실행될까요? 일반적인 구현방법에서는 세 줄이 실행됩니다. 따라서 swap은 호출 때마다 항상 같은 시간이 소요됩니다.

그렇다면 indexOfMinimum은 한 번 호출할 때마다 몇 줄의 코드가 실행될까요? 이것을 알려면 indexOfMinimum 안에 반복문이 몇 개나 되는지 알아야 합니다. indexOfMinimum 호출에 반복문이 몇 번이나 실행될까요? 반복문이 반복되는 하위배열 구간의 크기를 알아야 합니다. 만일 하위배열의 범위가 배열 전체라면 (첫 번째 단계의 경우에 해당) 루프는

n

번 실행됩니다. 만일 하위배열의 크기가 6이면 루프는 6번 돌게 되는 것이죠.

예를 들어 배열 전체의 크기가 8일 때 선택 정렬이 어떻게 이루어질지 생각해봅시다.

첫 번째 indexOfMinimum 호출에서는 배열의 모든 값을 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 8번 실행됩니다.
두 번째 indexOfMinimum호출에서는 하위 배열의 인덱스 1번부터 7번까지 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 7번 반복됩니다.
세 번째 호출은 하위 배열의 인덱스 2번부터 7번까지 보기 때문에 반복문 내부는 총 6번 반복됩니다.
네 번째 호출에서는 하위 배열 내 인덱스 3번부터 7번까지 반복문 내부가 총 5번 반복됩니다.
...
마지막으로 indexOfMinimum의 여덟 번째 호출에서 반복문은 한 번만 돕니다.

이렇게 나오는 indexOfMinimum의 반복문이 실행되는 횟수는 총 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36번입니다.

알아두기: 1부터 $n$ ‍까지 수의 합 계산하기

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1을 어떻게 빠르게 계산할 수 있을까요? 수를 더하기 쉽게 다시 배열하면 계산이 더욱 쉬워집니다. 먼저 가장 큰 수와 가장 작은 수를 더해 8+1을 해봅시다. 둘의 합은 9 입니다. 이제 그 다음으로 큰 수와 그 다음으로 작은 수를 서로 더해 7+2를 합시다. 둘의 합도 역시 9입니다. 6+3은 어떨까요? 마찬가지로 9입니다. 마지막으로 5+4를 합니다. 또 9가 나왔습니다. 그럼 이제 답을 구해볼까요?

\begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) & = 9 + 9 + 9 + 9 \\ = 4 \cdot 9 \\ = 36 . \end{aligned}

방금 한 계산에서는 총 네 쌍의 수를 더해 각각의 합이 9가 되도록 만들었습니다. 이제 연속하는 정수의 합을 쉽게 계산하는 방법을 일반화시켜 봅시다.

가장 작은 수와 가장 큰 수끼리 짝지어 서로 더합니다.
짝지은 수의 개수로 곱해줍니다.

만일 수열안에 숫자가 홀수 개수만큼 밖에 없다면 어떻게 할까요? 상관없습니다! 홀로 남은 수는 한쌍의 반으로 취급하여 계산하면 됩니다. 예를 들어 1 + 2 + 3 + 4 + 5를 계산해야 한다면 합이 6인 두 쌍(1+5와 2+4)의 수와 남는 수 한 개(3)가 있어 총 2.5 쌍의 수가 나옵니다. 이를 계산해보면

2.5 \cdot 6 = 15

란 답을 얻을 수 있습니다.

1 부터

n

까지 수의 합은 어떻게 구해야 할까요? 이와 같은 수열은 수학에서 등차급수라고 부릅니다. 여기서 가장 작은 수와 가장 큰 수의 합은

n + 1

입니다. 수가 총

n

개 만큼 있으므로

n / 2

개의 쌍을 만들 수 있습니다 (

n

은 홀수, 짝수 둘 다 가능). 따라서 1 부터 n 까지 수의 합은

(n + 1) (n / 2)

으로 나타내며

n^{2} / 2 + n / 2

으로도 바꿔서 쓸 수 있습니다. 이 식에

n = 5

일 때와

n = 8

일 때를 대입해서 확인해보세요.

선택 정렬에 대한 점근적 실행 시간 분석하기

선택 정렬에 소요되는 총 실행 시간은 세 부분으로 나눌 수 있습니다.

모든 indexOfMinimum 호출에 대한 실행시간.
모든 swap 호출에 대한 실행시간.
selectionSort함수 내 남아있는 나머지 반복문의 실행시간.

2번과 3번은 쉽습니다. swap은

n

번 호출되고 그때마다 같은 시간이 소요된다는 사실은 이미 알고 있습니다. 점근적 표기법 을 사용하면 swap을 호출하는데

Θ (n)

의 시간이 걸리는 것 또한 알 수 있습니다. selectionSort에 있는 나머지 반복문은 단지 반복문 변수를 비교하여 약간씩 변화를 주거나 indexOfMinimum와 swap을 호출하는 것 밖에 없으므로

n

번 반복되는 루프는

Θ (n)

만큼의 시간이 걸릴 것으로 예측 가능합니다.

1번, 모든 indexOfMinimum 호출에 대한 실행시간에서 알아야 하는 부분 중 가장 까다로운 부분은 이미 알고 있습니다. indexOfMinimum의 반복문은 매번 같은 시간이 소요됩니다. 첫 번째 호출에서 이 루프는

n

번 만큼 반복되며 그다음부터는

n - 1

n - 2

, 이렇게 줄어듭니다. 바로 전에 배웠듯이

1 + 2 + \dots + (n - 1) + n

이 등차급수며 일반항으로는

(n + 1) (n / 2)

또는

n^{2} / 2 + n / 2

으로 나타낼 수 있습니다. 따라서 indexOfMinimum의 모든 호출에 따른 소요시간은 어떤 상수와

n^{2} / 2 + n / 2

을 곱한 만큼입니다. Θ 표기법에서는 곱해주는 상수값이나 일반항에 들어간 1/2이나 하위항은 무시합니다. 결과적으로 모든 indexOfMinimum호출에 대한 실행시간은

Θ (n^{2})

입니다.

위의 실행시간을 모두 더해보면, indexOfMinimum 호출에서

Θ (n^{2})

, swap 호출에서

Θ (n)

, selectionSort 에서

Θ (n)

, 이렇게 모두 세 개입니다.

Θ (n^{2})

항은 이 중에서도 가장 유효한 항이므로 선택 정렬의 실행시간은

Θ (n^{2})

으로 정의할 수 있습니다.

또 알아야 할 것이 한가지 있습니다. 선택 정렬에서는 특별히 값이 바뀔만한 경우가 존재하지 않습니다. 입력값에 상관없이 indexOfMinimum 루프는 항상

n^{2} + n / 2

번 반복됩니다. 따라서 선택 정렬의 실행 시간은 모든 경우에

Θ (n^{2})

이라고 할 수 있습니다.

이제

Θ (n^{2})

으로 얻은 값에 따라 실제 실행시간이 어떻게 바뀌는지 살펴봅시다. 선택 정렬이

n

개의 값을 정렬하는데 대략

n^{2} / 10^{6}

초가 걸린다고 가정해 봅시다. 초기

n

값을 작게 잡아

n = 100

으로 둡시다. 그렇다면 실제로 선택 정렬을 실행하는데

100^{2} / 10^{6} = 1 / 100

초가 걸립니다. 매우 빠른 것 같지만

n = 1000

일 때는 어떨까요? 이때는

1000^{2} / 10^{6} = 1

초가 걸립니다. 배열은 10배 커졌지만, 실행 시간은 100배 길어졌습니다.

n = 1,000,000

일 때는 선택 정렬을 하는데

{1,000,000}^{2} / 10^{6} = 1,000,000

초, 일수로 계산하면 11.5 일 입니다. 배열의 크기를 1000배 늘리면 실행 시간은 백만 배나 늘어납니다!

대화에 참여하고 싶으신가요?

로그인

정렬 기준:

지민 박
6년 전 에 포스트 됨. 지민 박 ' 의 포스트“등차급수에 대해서 알수있었고 1부터 n까지의 ...”로 바로가기
등차급수에 대해서 알수있었고 1부터 n까지의 수의 합 계산하기를 알수있어서 좋은 정보였다
로그인 버튼로그인 버튼
(추천 3 번)
정답
- 홍지현(201820133)
  6년 전 에 포스트 됨. 홍지현(201820133)' 의 포스트“등차급수에 대해서 알 수 있었고 1부터n까지의...”로 바로가기
  등차급수에 대해서 알 수 있었고 1부터n까지의 수의 합 계산하기를 알 수 있어서 좋은 정보 였다
  로그인 버튼
  (추천 1 번)
박현준
4년 전 에 포스트 됨. 박현준' 의 포스트“예를 들어 배열 전체의 크기가 8일 때 선택 ...”로 바로가기
예를 들어 배열 전체의 크기가 8일 때 선택 정렬이 어떻게 이루어질지 생각해봅시다.
첫 번째 indexOfMinimum 호출에서는 배열의 모든 값을 봐야 하기 때문에 indexOfMinimum의 반복문 내부는 총 8번 실행됩니다.

윗부분에서, 첫번째 indexOfMinimum 호출을 했을때, 8번 반복이 된다는것이 이해가 가질않습니다. indexOfMinimum의 반복문에서 배열의 첫번째 인덱스와 (두번째, 세번째, ..., 여덟번째 인덱스)와 각각 비교를 하면 반복문이 7번 실행되는거아닌가요?

for(var i = minIndex+1; i < array.length; i++) {
if(array[i] < minValue) {
minIndex = i;
minValue = array[i];
}
}
로그인 버튼로그인 버튼
(추천 1 번)
정답
- jihunrock
  3년 전 에 포스트 됨. jihunrock' 의 포스트“indexOfMinimum 함수에는 for 문...”로 바로가기
  indexOfMinimum 함수에는 for 문을 시작하기 전에
  startindex 에 해당하는 값을 저장하는 부분 때문에 8번이라고 하는거 같습니다.
  
  var minValue = array[startIndex];
  var minIndex = startIndex;
  로그인 버튼
  (추천 2 번)

영어를 잘 하시나요? 그렇다면, 이곳을 클릭하여 미국 칸아카데미에서 어떠한 토론이 진행되고 있는지 둘러 보세요.

컴퓨터과학

코스: 컴퓨터과학 > 단원 1

알아두기: 1부터 n‍ 까지 수의 합 계산하기

선택 정렬에 대한 점근적 실행 시간 분석하기

대화에 참여하고 싶으신가요?

알아두기: 1부터 $n$ ‍까지 수의 합 계산하기