[질문] O(2^N) 보다 작으면 반드시 O(N^M) 꼴인가요?

[익명(147.47)]

이걸 수학갤에 올려야되나 여기에 올려야 되나 고민 좀 하긴 했는데...

어떤 알고리즘의 시간복잡도의 증가가 지수적 증가보다 느리다면

반드시 이를 upper bound하는 다항적 증가가 존재하나요...?

[다믜(damhiya)]

e^x / log x 될것 같은데

[브닌떼(172.58)]

수학적으로 증명해달라는 말 아님?

[다믜(damhiya)]

걍 대입해보면 아는걸 뭐 증명씩이나

[다믜(damhiya)]

생각해보니까 e^x / log x 도 그냥 지수시간이네;

[EN_SA(encludingsalt)]

2^(log^2 n), 2^sprt(n)?

[익명(147.47)]

적어도 뒤에껀 exp(sqrt(x)) vs x^M 은 t=sqrt(x) 로 바꾸면 exp(t) vs x^2M 이라 그대로인듯요

[익명(147.47)]

아 밑에 증명 보고 이해했습니다

[아나리쿠(am5am)]

수학갤이랑 ps갤에서 고민해야지 왜 여기서 고민하누

[익명(147.47)]

아

[SPXL(sp500)]

https://en.m.wikipedia.org/wiki/Complexity_class
맞는것같은데..?
complexity class hierarchy에서 EXP 아래에 NP, P 있어서.. - dc App

[SPXL(sp500)]

정리하면. o(EXP) 이면 O(NP or P) 임 - dc App

[SPXL(sp500)]

o(EXP)이면 O(NP)인듯? - dc App

[익명(147.47)]

알아봐주셔서 감사해요 근데 제 질문은 O(EXP)보다 작고 O(P)보다 느린 시간복잡도의 존재여서 약간 결이 다른 듯..

[익명(49.174)]

하다못해 O(1.5^N)도 있는데

[익명(147.47)]

그건 걍 지수잖아요 의미 없음

[익명(49.174)]

헛소리했네 ㅎㅎ

[다믜(damhiya)]

임의의 b>1 에 대해서 O(b^n)이고 임의의 p>0에 대해서 O(n^p) 가 아닌 함수가 있는지가 정확한 표현같은데 아마 있을거라고 생각

[다믜(damhiya)]

e^(sqrt x)

[다믜(damhiya)]

lim e^(sqrt x) / x^p 에 로피탈 쓰면 e^(sqrt x) / 2p x^(p-1/2) 니까 귀납적으로 적용하면 lim e^(sqrt x) / x^p = inf임. 그리고 lim e^(sqrt x) / b^x = lim e^(sqrt x - (log b) x) = 0

[익명(147.47)]

지수보다 반드시 느리고 다항보다 반드시 빠른 거 맞네요 감사합니다

[익명(147.47)]

로피탈 귀납 까지 안 가고 t=sqrt(x) 로 놓고 치환만 해도 되는 거 같아요

[익명(211.250)]

이 정도 수학적 스킬은 있어야 ps갤 완장인건가? 미적 다 까묵음 ㅎㅎ

[익명(49.174)]

log O를 보면 쉽게 찾겠다 x^(log x) 같은거