exponential과 factorial의 대소를 묻는 문제입니다
에를 들어 2**n 과 m!중 어느 수가 더 큰가를 묻는 문제입니다. 그리고 n!=m입니다.
저는 두개 경우 각각 Dynamic programming으로 두개의 function (exponential(n)과 factorial(m))으로 식을 만든 후에 대소 비교를 하는 방식으로 풀었는데요.
n 과 m이 심하게 큰경우에는 아얘 돌리지를 못하네요 ㅠㅠ 예를 들어 n=99999999, m=345080 이런경우요.
직관적으로 어느 수가 더 큰지 알수 있는 방법이 있나요?

다시 말씀드리지만 n과 m은 같지 않습니다. (만약 같다면 문제가 굉장히 쉬워져서요)

답변감사합니다.

PS: 해결 했습니다. 답변 주신분들 감사합니다.
Solution1: https://math.stackexchange.com/questions/1357884/comparison-between-exponential-and-factorial-results 여기 있는데로 해보세요
Solution2: Solution2랑 다를게 없는데요. 그냥 log(m!)= log(m)+log(m-1)+…+log(2)+log(1)이렇게 되잖아요. 근데 Multiplication의 경우보다 합이 훨씬 빠르네요. 그래서 엄청 큰 수도 그냥 풀어 버리네요.

Factorial 은 dynamic programming으로 recursive하게 풀어도 iterative한 solution보다 running타임 오래걸려요. 애초에 recursion 자체가 콜스텍이 커지면 커질수록 연산속도가 오래걸려요. 같은 횟수를 iterative 하게 돌리고 recursive하게 돌리면 iterative가 훨씬 빨라요. 일단 factorial은 iterative하게 bottom up solution으로 빌드업하시면 거기서 러닝타임 세이브하실거에요.

네 답변감사합니다. 시험볼때도 두개 모두 말씀하신데로 bottom up solution으로 했어용! 할수 있는 방법은 다 해봤는데 dp자체가 수가 엄청 클때는 안되더라구요 ㅠㅠ. 일본회사인데 미국회사랑 달리 그냥 방법만 물어보는게 아니라 input value가 어마어마하더라구요 ㅠㅠ

이게 왜 programming 문제인지? 수학 문제인데..

I remember ln(n!) ~= n* ln(n) .. I think there’s an inequality you can use..

OK. I just looked it up. The inequality is:

n * ln (n/e) + 1 <= ln (n!) <= (n+1) * ln ((n+1) / e) + 1

You can use above to filter out most big m and n. (obviously, you need to compare it with ln (2**n) == n * ln (2) )

1. you first take log of m and use the above inequality to essentially filter out most m and n input combination.

But your professor would surely to have m and n pairs that can’t be filtered out using above inequality. Then, you would have to calculate actual number in order to compare, but problem is the number can be very very big and you’re going to run into all sorts of problems (even if you’re using big number package). Below is what I would do.

2. count the number of factor of 2 in the factorial ( m! ), and subtract them from n. I think you can do this systematically by building a table. and then you do the multiplication of the remaining numbers.

Online Coding Test문제였어서 programming 문제라고 생각했지요. 문제 풀면서 뭔가 방법이 있을거 같은데 라고 계속 생각했는데 뭐 하는 도중에는 생각하기 힘들잖아요. 어쩄든 감사해요 !

이거한번봐보세요! https://math.stackexchange.com/questions/1357884/comparison-between-exponential-and-factorial-results

감사합니당!! 아 뭔가 허무하네요 ㅠㅠ ㅋㅋㅋㅋㅋ

꼭 스털링 같은거 외워서 안 쓰더라도, 로그 씌우는 접근으로 문제를 시간 안에 풀 수 있도록 말이 되게 바꿀 수 있습니다.

위에 써주신 분이 링크가 말씀하신거랑 같아요. 감사합니다