分布式复杂性

（计算机科学技术）

分布式复杂性（distributional complexity），计算机科学技术名词，一个算法 A 对输入分布 D 的分布式复杂性，记为 d(A，D) ，定义为 d(A，D) =，这里 D(x) 是输入 x 按分布 D 出现的概率，cost (A，x) 是输入 x 在算法 A 上的计算复杂性，是随机变量cost (A，D) 的期望值。