On Malign Input Distributions for Algorithms

スポンサーリンク

概要

• 論文の詳細を見る

• By a measure we mean a function μ from {0,1}^* (the set of all binary sequences) to real numbers such that μ(x)≧0 and μ({0,1}^*)<∞. A malign measure is a measure such that if an input x in {0,1}^n (the set of all binary sequences of length n) is selected with the probability μ(x) / μ({0,1}^n) then the worst-case computation time t^A(n) and the average-case computation time t^A(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitanyi found that measures that are known as a priori measures are malign. We prove that "a priori"-ness and malignness are different in one strong sense.

• 一般社団法人電子情報通信学会の論文
• 1993-06-25

著者

• Kobayashi Kojiro

  Faculty Of Engineering Soka University

• Kobayashi Kojiro

  Faculty Of Science Tokyo Institute Of Technology

関連論文

• On the Tree Structure of Some Worst Inputs for Heapsort (Special Issue on Selected Papers from LA Symposium)
• On Malign Input Distributions for Algorithms

スポンサーリンク