O(루트(log(N!)))와 O(N) 둘 중에 무엇이 더 빠를까?

[익명(211.168)]

ln(x!)=ln(1)+ln(2)+...+ln(x)=ln(x)(ln(x)+1)/2

그래서 결론은 둘다 시간복잡도가 같음

[익명(rjsdn3458)]

저식이 성립함? - dc App

[익명(211.168)]

ln(ab)=ln(a)+ln(b)

[익명(rjsdn3458)]

아니 그 뒤쪽에 식이 성립안하잖아 - dc App

[익명(211.168)]

루트(x제곱+x)가 x보다는 항상 크기 때문에 전자가 더 느릴 수도 있음

[익명(rjsdn3458)]

공차가 1이 아닌데 - dc App

[익명(211.168)]

엇... 그렇네

[프갤로(gotopg)]

성립안될듯ㅇㅅㅇ

[익명(211.168)]

세제곱근하면 전자가 더 빨라지려나

[익명(rjsdn3458)]

전자가 더 느린건 확실함 - dc App

[익명(211.168)]

전자가 더 빠를듯

[익명(rjsdn3458)]

전자가 훨씬 느리지 수학못함? - dc App

[익명(211.168)]

아랫댓도 전자가 더 빠르대

[익명(rjsdn3458)]

내가 증명 다시함ㄱ - dc App

[익명(14.32)]

전자가 더 빠르지 않어? N! < N ^ N 이니까 전자는 아무리 커봐야 루트(N * logN) 이잖어. 그럼 빠른건 닥전아닌가? 뭔가 틀렸냐?

[익명(211.168)]

환원이 이렇게 가능하네 ㄷㄷ

[익명(14.32)]

log 가 사기캐이긴 하다

[익명(rjsdn3458)]

https://m.dcinside.com/board/programming/2368606
- dc App