연산회수 세는 방법좀 알려주세요ㅠ
멱부리
2023.04.01
질문 제목 :연산회수 세는 방법좀 알려주세요ㅠ
연산회수를 정확히세는 방법을 잘모르겠어요
질문 내용 : 연산회수를 정확히세는 방법을 알고싶습니다.
제가 세는 방식은 이렇습니다. 잘모르겟어요 ㅠ
int test(int n)
{
int i;
int total=1; 대입한번
for(i=2;in;i++){ 대입한번, 비교 n-2, 증감 n-2
total *= n; 연산 n번 (여기에서 대입따로 곱셈따로해서 2n번인지 n번인지..)
}
return n;
}
이것은 1+1+(n-2)*2+n = 3n-4+2 = 3n-2 =o(n)
void sum(int n)
{
int i,b;
b=2; 대입한번
i=1; 대입한번
while(i = n){ n번의 비교
i = i*b; n번의 연산
}
}
2n+2 = o(n)
저는 이렇게 생각하는데
다른 분들한테 여쭤보니까 반복문은 제외한다던지 어떤분은 2번이 o(log2(밑)n) 이라던데
정확한 지식을 쌓고싶습니다 더와주세요
