반복(Loop)
글쓴이: rgbi3307 / 작성시간: 수, 2010/10/20 - 11:25오전
loop01 (int n)
{
int i1, i2;
for (i1 = 0; i1 < n; i1++)
for (i2 = 0; i2 < n; i2++)
;
}
loop02 (int n)
{
int i1, i2;
for (i1 = 0; i1 < n; i1++)
for (i2 = i1; i2 < n; i2++)
;
}
loop03 (int n)
{
int i1, i2;
for (i1 = 0; i1 < n; i1++)
for (i2 = 1; i2 <= n; i2*=2)
;
}
loop04 (int n)
{
int i1, i2;
for (i1 = 0; i1 < n; i1++)
for (i2 = n; i2 > 0; i2/=2)
;
}
loop05 (int n)
{
if (n > 0) {
loop05 (--n);
loop05 (--n);
}
}
loop06 (int n)
{
if (n > 0) {
loop06 (n/=2);
loop06 (n/=2);
}
}위의 여섯가지 함수 중에서 반복회수가 가장 작은것과 큰것은 어느것일까요?
From:
*알지비 (메일: rgbi3307(at)nate.com)
*틈틈히 커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
Forums:
가장 큰 것 01, 가장 작은 것 06
01 N제곱
02 (N제곱 + N)/2
03 N*(floor(lnN)+1)
04 03과 같음
05 피바노치에 대한 식이 있나요...? 대강 N제곱보다 약간 안나올듯
06 05에 제곱근
N의 크기에 따라서 달라지겠습니다만
Big O 로 따지면 [01, 02, 05] > [03, 04] > [06]
맞나요???
알고리즘 분석법에 맞게 하신듯 합니다.
N의 개수를 4, 8, 16... 으로 했을때 아래와 같이 반복(Loop)회수가 실습되었습니다.
---------------------------------------- 4 8 16 n ---------------------------------------- Loop01 16 64 256 n제곱 Loop02 10 36 136 n(n+1)/2 Loop03 12 32 80 n(lg(n)+1) Loop04 12 32 80 n(lg(n)+1) Loop05 7 54 2583 ?? Loop06 4 7 12 ?? ----------------------------------------실습결과에서 Big O 로 따지면 아래의 관계가 성립합니다.
n이 8보다 적으면,
[01, 02, 05] > [03, 04] > [06]
n이 8보다 크면,
[05, 01, 02] > [03, 04] > [06]
즉, n이 8보다 크면 Loop06의 반복회수가 가장작고, Loop05의 반복회수가 가장 큽니다.
Loop06, Loop05의 반복회수를 계산하기 위한 정규식은 어떻게 산출할 수 있을까요?
(재귀호출은 여전히 어렵군요)
From:
*알지비 (메일: rgbi3307(at)nate.com)
*틈틈히 커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))