수다닷컴

질문 내용 : 대학교책 연습문제를 푸는데 답은 아는데 정확히 이해가 가지 않습니다 ㅜㅜ

책을보면서 혼자 독학할려고해도 안되 다시 여기다 도움을 청합니다 ㅜ 왜 답이되는지 해설 비슷하게 설명해주실수있나요ㅜㅜ

부탁드리겠습니다.

6.O(n²)의 시간 복잡도를 가지는 알고리즘에서 입력의 개수가 2배로 되었다면 실행 시간은 어떻게 되는가?

(1)변합없다 (2)2배 (3)4배 (4)8배
답:(3)

9. 다음코드에서 대입 연산, 곱셈, 덧셈 연산, 비교 연산의 개수를 계산하여 시간 복잡도 함수를 계산해보라.
(1) test(int n)
{
int i;
int total=1;1번의 대입연산
for(i=2;in;i++){루프 제어 문자은 무시
total *= n; n-2번의 곱셈과 대입연산
}
return n;
}
- 1+n-2+n-2번의 연산 -

(2)
float sum(float list[], int n)
{
float tempsum;
int i;
tempsum = 0; 1번의 대입연산
for(i=0;in;i++) { 루프제어 연산 무시
tempsum += list[i]; n번의 대입연산, 덧셈연산
}
tempsum += 100; 1번의 대입연산, 덧셈연산
tempsum += 200; 1번의 대입연산, 덧셈연산
return tempsum;
}
- 1+n+n+2+2 -

(3)
void sum(int n)
{
int i,b;
b=2; 1번의 대입연산
i=1; 1번의 대입연산
while(i = n){ 루프 제어 연산 무시
i = i*b; 번의 곱셈, 대입 연산
}
}

- 1+1+ + -

14.다음 프로그램의 시간 복잡도를 빅오 표기법으로 나타내라

(1) for (i =0; i n; ++i) ++k;

(2) for (i =1; i n; I *=2) ++k;

(3) for (i =n-1; I !=0; I /=2) ++k;

(4) for (i =0; i n; ++i)
if(i % 2 ==0)
++k;
(5) for (i =0; I n; ++i)
for (j =0; j n; ++j)
++k;
(6) for (i =0; I n; ++i)
for (j = i; j n; ++j)
++k;
(7) for (i = 0; I n; ++i)

18. 다음의 프로그램 코드에 대하여 답하라

int i, k;

for(i=0; i(n-2); i++){루프 제어 문장 무시

for(k=0; k30; k++){루프 제어 문장 무시

buffer[i][k] = 0;30*(n-2)번 수행

}

}

(1) 다음 알고리즘의 시간 복잡도를 n에 대한 함수로 나타내고, 빅오 표기법으로도 나타내어라. 여기서. 여기서 입력의 개수는 양의 정수n이다.

(2) 위의 프로그램에서 입력의 개수도 100배 증가하였고 cpu의 속도도 100배 증가하였을 경우, 위의프로그램의 실행 시간이 늘어나는가? 아니면 줄어드는가? 그이유는?

20. 배열에 정수가 들어 있다고 가정하고 다음 작업의 최악, 최선의 시간 복잡도를 빅오 표기법으로 말하라.

(1) 배열의 n번째 숫자를 화면에 출력한다.- 최악 O(1) 최선 O(1)

(2) 배열안의 숫자 중에서 최소값을 찾는다.- 최악 O(n) 최선 O(n)

(3) 배열의 모든 숫자를 더한다.- 최악 O(n) 최선 O(n)

신청하기