Measuring Cost

Loops and Input Size


반복문의 겹 수보다 실제 실행 범위를 읽는다. 연속된 반복은 더하고, 독립적인 중첩은 곱하고, 안쪽 길이가 달라지면 줄마다 더한다. 칸 하나가 안쪽 문장 한 번의 실행이다.

한 번의 순회와 연속 반복원소 하나마다 한 번 실행되고, 나란한 두 반복문은 m + n으로 더한다.
독립적인 중첩바깥 한 단계마다 안쪽을 처음부터 다시 실행하므로 곱한다.
삼각 범위행 i에서 i개를 실행해 0부터 n − 1까지 더한다.

반복 구조에 따라 실행되는 칸의 수와 순서가 달라진다

실행 칸의 수가 곧 정확한 실행 횟수이며, 삼각형을 맞추기 위한 빈 칸은 실행 횟수에 포함하지 않는다.

칸 하나가 반복 본문 한 번의 실행이다. 연한 초록 칸은 이미 실행한 칸, 진한 초록 칸은 지금 실행하는 칸이고, 빗금 칸은 배치를 맞춘 빈 칸이라 실행 횟수에서 제외한다.

같은 크기에서 범위별 정확한 수를 나란히 읽는다

아래 비교도 위의 m과 n을 사용한다. 반복문의 겹 수가 아니라 각 범위의 실제 길이가 비용식을 정한다.

한 번의 순회

n개 원소를 한 번씩 처리한다.

연속된 두 반복문

각각 센 뒤 더한다. mn이 아니다.

두 목록의 모든 쌍

두 크기를 하나의 n으로 합치지 않는다.

독립적인 중첩

n개 행마다 n개 열을 실행한다.

안쪽이 상수 범위

두 겹이어도 안쪽 길이가 3으로 고정이다.

삼각 범위

0 + 1 + ··· + (n - 1)을 더한다.

안쪽 범위가 상수인지, n인지, 바깥 인덱스 i인지 먼저 확인한다.