3.1.1 亚线性时间算法
随着许多应用中数据规模的指数级增长（例如社交网络、基因组学和互联网规模的数据），传统的多项式时间（甚至线性时间）算法由于其不断增加的计算需求而变得不切实际。在面对如此庞大的数据量时，我们迫切需要运行时间比输入大小都要小很多的算法，这种算法被称之为亚线性时间算法。亚线性时间算法的基本思想是利用随机抽样的方法，观测输入对象（如大图）的局部信息，通过这些信息来近似地推断整个输入的全局性质或估计其参数。这种方法为我们提供了一种高效处理大规模数据集的新途径，使得即使是海量数据，也能在可接受的时间内进行有效处理。
在过去的二十几年里，以性质检测为代表的亚线性时间算法一直是理论计算机科学领域的研究热点。性质检测主要关注如何高效且近似地测试给定对象（如图或函数）是否满足某种性质或远离满足该性质。它的主要目标是通过少量的查询，而不是对整个对象进行详尽分析，来确定对象是否具有特定性质。性质检测在计算几何、图论和机器学习等各个领域都有广泛应用。它可以高效验证大型数据集或复杂结构的性质，并对现实世界中的算法设计和数据分析产生重要影响。性质检测的研究带来重要的算法技术，并加深了对各种问题计算复杂性的理解。
图性质检测是用于快速判定一个图是否满足某个性质（如连通性、二部性、3-可着色性、平面性等）的亚线性时间算法。我们也可以对 图中不同的重要参数进行快速估计，设计近似最小生成树权重、边数、最大匹配数、子图个数等参数的亚线性时间算法。更进一步，当输出
结构很大时（如图的最大匹配），我们可以设计相应的局部计算算法，允许用户“探测”大输出中的局部位置信息（如查询某条边是否属于最大匹配）；对于每次“探测”，算法对输入图做尽可能少的查询。