算法挑战

yuange1975

取了前20位显示
500，323秒
100，1秒

过几天用Julia编写一个直接编译执行的，和python解释执行的对比一下，看看执行时间如何。


=============wayne编辑,没必要上传图片,已经删除, 并补充更详细的答案
$(32243281478661245117275486119293967823731<<697226>>837906321426336396254777203086925844822511)/(30806209830441890018345910868023659832515<<697222>>000000000000000000000000000000000000000000)$

wayne

PARI/Gp代码,  跟前面的Mathematica代码的算法复杂度一样,$O(n*n*m)$, 但是运行速度好像比Mathematica慢不少.

1. 
   
2. default(parisize, 1000000000)
   
3. func(x,y) =
   
4. {
   
5.     y^(-1 - x)*x!;
   
6. }
   
7. 
   
8. nm(n,m) =
   
9. {
   
10.     g=0;
    
11.     p = 0;
    
12.     for(i=0,m-1,p+=1/i!*x^i);
    
13.     p = 1-(1-y*p)^n;
    
14.     for(j=1,n,cf=polcoef(p,j,y);
    
15.         for(xx=0,j*(m-1),g+=polcoef(cf,xx,x)*func(xx,j)));
    
16.     n*g
    
17. }
    
18. 
    
19. nmp(n,m) =
    
20. {
    
21.     g=0;
    
22.     p = 0;
    
23.     for(i=0,m-1,p+=1/i!*x^i);
    
24.     p = 1-(1-y*p)^n
    
25. }
    

复制代码

yuange1975

这个正常，这就是MMA平台的速度。

大致就是O(M*N*N)=c*M*N*N，不同平台不同实现代码大致有不同的c。

前面大致你的100和500的时间对比，以及我的时间对比，已经看出你的算法基本上也是N*N*M的复杂度了，只是实现代码和平台之间的c的差距。其实这个代码优化对c的影响也不小。

nyy

挑战个啥？连注释都没有的代码，谁愿意看