单元探测模型

（理学 | 计算机科学技术）

单元探测模型（cell probe model），理学-计算机科学技术-计算机科学理论-算法-数据结构，一个类似于随机存储器（RAM）的计算模型，但它只统计存储访问的操作次数。此模型通常用于证明算法和数据结构的下界。数学定义给定一个数据集合S，构造一个拥有c个存储单元、每个存储单元w比特的数据结构。当给定一个待查询的元素s，要在访问至多t个存储单元的情况下以1-ε的正确率回答元素s是否属于集合S，这称为基于c单元w比特大小的ε-错误t-探测算法。