资源描述:
《Summation of series has the same exponent and the base numbers》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、SummationofserieshasthesameexponentandthebasenumbersinaarithmeticprogressionincomputationalcomplexityLiuAi-JunFanJing-BoYuXian-FengDepartmentofcomputerscience,ShangLuoUniversity,ShangLuo,China,726000Abstract:Thecomputer'sadvantageliesinit’sautomation,Problemthatcanbesolvedbyalgebracanalso
2、berealizedthroughprogramming.Oncetheproblemcanuseprogramsolved,therewillonlybeinputandoutput.Algorithmqualitymainlyliesinthecomputationalcomplexity.Socomplexityalwaysisoneofresearchhotspotproblemsofcomputerscience.Duringcomplexitycalculationprocesswilloftenmeetaproblemthatcalculatingthesu
3、mmationofaserieshasthesameexponentandit’sbasenumberisaarithmeticprogression.Thearticlestartfromasimpleproblem,giveseveralmethodstosolvetheproblem,andspreadtheproblemstotheirgeneralcase.Keywords:complexity;series;crackterm;undeterminedcoefficient1ProblemTalkfromasimplecomplexitycalculation
4、problem,theproblem[1]iscalculatingtheexecutionnumberofx=x+1inthefollowingprogram.for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;Remembertheexecutiontimesofx=x+1asthen,(Ⅰ)Definition1Formif,isaproblemthatsummationofserieshasthesameexponentandthebasenumberisaarithmeticprogressionin
5、computationalcomplexity(SimplenotesforSBACC).Proposition1Innature,analogously,areallSBACCs.Forexample,,,……ProofWesayisalsoaSBACCbecause,,SocanbedividedintoSBACCsand.Generally,,Soanalogously,areallSBACCs.Proposition1isreasonable.2Severalmethodstosolvetheproblem2.1Risetheexponenttospreadand
6、offsetunderdislocationIfwecancalculate(Ⅰ)(2),thenwewillgetthesolutionof.Putbothsidestogether,eachequationontheleftwilloffsetwiththefirstterminthepreviousequationontheright.(Ⅱ)Calculatefrom(Ⅱ)(1)weget,(Ⅲ)Push(Ⅲ)into(Ⅰ)(3)get,.Similarly,canbecalculatedasfollow,Offsetunderdislocation[2]eache
7、quationontheleftoffsetwiththefirstterminthepreviousequationontheright,thengetTheorem1asfollow.Theorem1,.Remark1Theresultoftheorem1isaregressionequation.2.2CracktermstooffsetforsummationWecalculate(Ⅰ)(1)togetthesolutionof.Wedirectlycalculatethemoregeneralform.Crackte