vector factor(int n) {
if (n == 1) return vector(1,1);
vectorret;
for (int div = 2; n > 1; ++div) {
while (n % div == 0)
{
n /= div;
ret.push_back(div);
}
}
return ret;
}
이 알고리즘이 지수 시간이 걸리는 알고리즘이라던데
어째서 지수시간인가요... n아닌가 ㅠㅠ
백터에 많은 수가 삽입되면 백터 늘리는데 늘어가는 시간때문에 지수시간이라 한건가 ㅠㅠ
대충 보는데
지수시간? 로그시간이아니고?
입력크기 n에 대해 지수시간이 걸린다네요
지수 시간이란 게 몇 페이지에 나와있는데
p105 마지막줄이요
'입력의 크기를 입력이 차지하는 비트 수로 정의하면' 지수 시간이 걸린다는 거잖아
지문 꼼꼼히 읽자
그 말이 무슨말인지 모르겠습니다 ㅠㅠ
입력을 x라고 했을 때 저 코드는 O(x)이고, n = x가 차지하는 비트 수 = ceil(log2 x)이라고 정의하면 O(2^n)이 된다는 말임. x = 2^(log2 x) ≈ 2^n니까 표현만 다른 동일한 식임.
저 코드 자체는 O(n)임. 간단한 최적화로 O(sqrt(n))이 되고.
그렇군요 감사합니당.
아 감사합니다.