PerformanceMeasurement

PerformanceMeasurement
ThereareatleasttwodifferentalgorithmsthatcancomputeXNforsomepositiveintegerN.Algorithm1istouseN–1multiplications.Algorithm2worksinthefollowingway:ifNiseven,XN=XN/2XN/2;andifNisodd,XN=X(N–1)/2X(N–1)/2X.Figure2.11inyourtextbookgivestherecursiveversionofthisalgorithm.Yourtasksare:(1)ImplementAlgorithm1andaniterativeversionofAlgorithm2;(2)Analyzethecomplexitiesofthetwoalgorithms;(3)MeasureandcomparetheperformancesofAlgorithm1andtheiterativeandrecursiveimplementationsofAlgorithm2forX=1.0001andN=1000,5000,10000,20000,40000,60000,80000,100000. 本软件ID:5281161