O(루트logn!)와 O(n) 시간 복잡도 증명(전자가 느림)

[익명(rjsdn3458)]

ln n! = ln1+ln2+....lnn < 1+2+3...n = n(n+1)/2

양변에 루트를 취해주고 n->inf 로 보내면

후자는 시간 복잡도가 O(n)이고

전자는 O(루트logn!)임

수렴하지도 않고 무조건 후자가 빠름

- dc official App

[프갤로(gotopg)]

팩토리얼 무시무시해ㅇㅅㅇ

[익명(14.32)]

증명이 안되 잖어 잘 모르겠으면 계산기에라도 넣어봐 루트(NlogN) vs N 정도로 계속 간다.

[르딩(112.170)]

증명은 안되는데 후자가 빠를거같은데

[익명(rjsdn3458)]

극한으로 가면 무한대로 가는건 확실함 - dc App

[익명(14.32)]

N! < N ^ N 이니까 전자는 아무리 커봐야 루트(N * logN) 이잖어. 이게 어떻게 후자가 더 빨라.. ㅜ

[익명(rjsdn3458)]

전자가 아무리 커봐야 그거니깐 후자가 빠르지 너가한말 다시읽어봐 - dc App

[익명(rjsdn3458)]

루트nlongn vs 루트 n*n이니 당연히 후자가 빠르네 - dc App

[익명(14.32)]

아니 씨 숫자가 작아야 빠르지 무슨소리야

[익명(rjsdn3458)]

아 그 말이었냐 ㅋㅋㅋ 같은얘기하고있었네 난 n->무한대 관점에서 더 빠르게 증가한다고 말한거였음 - dc App

[익명(rjsdn3458)]

알고리즘은 시간으로 보니 너가 맞음 - dc App