0
喜欢
0
书签
声明论文
The Analysis of Find or Perpetuities on Cadlag Functions   
摘  要:   In the running time analysis of the algorithm Find and versions of it appear as limiting distributions solutions of some stochastic fixed points equation of the for m X D = ∑ i AiXi± Bi+C on the space D of cadlag functions. The distribution of the D-valued process X is invariant by some random linear affine transformation of space and some random time change. We show the existence of solutions via the Weighted Branching Process. Specifically we present m-median and adapted versions of Find. For an optimal adapted version the normalized asymptotic number of comparisons needed satisfies the degenerate fixed point equation ¡ X(s) ¢

共享有1个版本

Bibtex
创新指数 
阅读指数 
重现指数 
论文点评
还没有人点评哦

Feedback
Feedback
Feedback
我想反馈:
排行榜