Abstrakt. Vi anser att problemet med att utveckla automatiserade tekniker för att lösa återkommande relationer för att hjälpa den förväntade-runtime analys av program. Flera klassiska lärobok algoritmer har ganska effektiv förväntad-runtime komplexitet, medan motsvarande värsta fall gränser är antingen ineffektiva (t.ex., QUICK-SORT), eller helt ineffektiv (t.ex., COUPON-KOLLEKTOR). Eftersom huvudfokus för analys av förväntad körtid är att erhålla effektiva gränser, anser vi att gränser som antingen är logaritmiska, linjära eller nästan linjära (O(log n), O(n), O(n · log n), respektive, där n representerar ingångsstorleken). Vårt huvudsakliga bidrag är ett effektivt (enkel linjär-tid algoritm) ljud tillvägagångssätt för att härleda sådana förväntade-runtime gränser för analys av återfallsrelationer som induceras av randomiserade algoritmer. Vårt tillvägagångssätt kan sluta sig till de asymptotiskt optimala gränserna för förväntad körtid för upprepningar av klassiska randomiserade algoritmer, inklusive RANDOMIZED-SÖKNING, QUICK-SORT, QUICK-SELECT, COUPON-KOLLEKTOR, där de värsta fallgränserna antingen är ineffektiva (såsom linjära jämfört med logaritmiska av förväntad körtid, eller kvadratiska jämfört med linjära eller nästan linjära av förväntad körtid), eller ineffektiva. Vi har implementerat vår strategi, och de experimentella resultaten visar att vi får gränserna effektivt för upprepningar av olika klassiska algoritmer.
Chatterjee m.fl. I Ref föreslås en teknik för att lösa återkommande relationer som uppstår i analysen av förväntade kostnader i drifttid.
Automated Recurrence Analysis for Almost-Linear Expected-Runtime Bounds
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}