수다닷컴

질문 제목 : 시간복잡도 계산입니다 . 도와주세요 ㅠㅠ 질문 요약 :아래의 질문입니다 ㅠㅠ 질문 내용 :
다음 프로그램에서 각 문장의 수행 횟수를 분석하고 시간 복잡도(time complexity)를 O(big O)기호로 나타내시오.
(N이 입력으로 주어짐.)
(코드 1)

sum = 0;
for (i = 0; i N; i++)
for (j = 1; j = N; j = j * 2)
sum = sum + j;
for (i = 0; i N; i++)
sum = sum - i;

step count =
time complexity = O( )

(코드 2)

i = N;
while (i 1) {
i = i / 2;
for (j = 0; j 1000000; j++)
sum = sum + j;
}

step count =
time complexity = O( )

(코드 3)

sum = 0;
d = 1;
d = (d N);
for (i = 0; i d; i++)
for (j = 0; j 1000000; j++)
sum = sum + i;

step count =
time complexity = O( )
Hint: 는 C언어에서 왼쪽으로 1비트 쉬프트하는 연산자임.

신청하기