수다닷컴

어느 게시판에 올려야 하나 고민고민하다가
그래도 C언어로 되어있어서(???) 올립니다(-퍽)

매직 스퀘어라는 프로그램인데, 1에서 n제곱(2제곱) 까지의 정수로 된 n x n 행렬로
각 행과 열과 2개의 주대각선의 합이 모두 같아요~

3 입력하면

6 1 8
7 5 3
2 9 4

이렇게 출력됩니다~

튼 복잡도 분석은 아래와 같다고 하네요^^;;;

n의 값에서 오류 여부를 판단하기 위한 if명령문은 θ(1)의 시간이 걸린다.
2개의 중첩된 for 루프의 복잡도는 θ(n제곱)이다.
그 다음 for 루프를 한번 실행하는데는 θ(1)의 시간이 걸린다.
이 루프는 θ(n제곱)번 반복되어 복잡도는 θ(n제곱)이 된다.
정방형을 출력하는 이중 for루프도 θ(n제곱)의 시간이 걸려서
매직스퀘어 프로그램의 점근적 복잡도는 θ(n제곱)이다.

제가 이해가 안 가는 부분은

그 다음 for 루프를 한번 실행하는데는 θ(1)의 시간이 걸린다.
이 루프는 θ(n제곱)번 반복되어 복잡도는 θ(n제곱)이 된다.

입니다ㅜ_ㅜ

for 루프 한번 실행하면 θ(n)의 시간이 걸리지 않나요?
그리고 이 루프가 왜 θ(n제곱) 번 반복되나요?

책에는 for 루프 2번 돌리는 것만 점근적 복잡도 설명되어있고
for 루프 한번은 그 한 줄밖에 안 써있어서 잘 이해가 안 갑니다ㅜ_ㅜ
알려주시면 감사하겠습니다^_^#include stdio.h
#define MAX_SIZE 15 /* 정방형의 최대 크기*/
void main(void)
{ /*정방형을 반복적으로 생성*/
static int square[MAX_SIZE][MAX_SIZE];
int i, j, row, column; /*지수*/
int count; /*계수*/
int size; /*정방형의 크기*/
printf(Enter the size of the square : );
scanf(%d, &size);
/*입력에 오류가 있는지 체크*/
if(size 1 || size MAX_SIZE +1) {
fprintf(stderr, Error! Size is out of range\n);
exit(1);
}
if(!(size % 2)) {
fprintf(stderr, Error! Size is even\n);
exit(1);
}
for(i = 0; j size; j++)
for(j = 0; j size; j++)
square[i][j] = 0;
square[0][(size-1) /2] = 1; /*첫 번째 행의 중앙에 1을 넣는다*/
/*I와J는 현재 위치*/
i = 0;
j = (size - 1) /2;
for(count = 2; count = size * size; count++) {
row = (i - 1 0) ? (size - 1) : (i - 1); /*위로*/
column = (j - 1 0) ? (size - 1) : (j - 1);/*아래로*/
if(square[row][column])
i = (++i) % size;
else { /*정방형이 비어있는경우*/
i = row;
j = (j - 1 0) ? (size - 1) : --j;
}
square[i][j] = count;
}
/*정방형을 출력*/
printf(Magic Square of size %d: \n\n, size);
for(i = 0; i size; i++) {
for(j = 0; j size; j++)
printf(%5d, square[i][j]);
printf(\n);
}
printf(\n\n);
}

신청하기