近似最近邻 (ANN) 搜索算法的时间复杂度因方法而异，但大多数旨在实现相对于数据集大小的亚线性查询时间。常见的算法如 k-d 树、局部敏感哈希 (LSH) 和分层可导航小世界 (HNSW) 都有不同的权衡。例如，k-d 树在平衡情况下可实现 O(log n) 的搜索时间，但在高维空间中会退化到接近线性的 O(n)。LSH 通常通过哈希表查找实现平均 O(1) 的查询时间，但这取决于参数，如哈希函数的数量。HNSW 是一种基于图的方法，由于其分层结构能有效缩小搜索区域，因此提供 O(log n) 的搜索复杂度。这些理论复杂度表明查询速度优于线性的暴力搜索方法 (O(n))，但实际性能在很大程度上取决于实现和数据集特性。
在实践中，复杂度与实际速度之间的关系是微妙的。例如，HNSW 即使在十亿级数据集上也能提供快速查询，因为其对数级缩放减少了距离计算次数。然而，常数和开销也很重要：虽然 HNSW 的搜索步骤很快，但构建索引需要 O(n log n) 时间和大量内存。类似地，LSH 的 O(1) 查找假定哈希经过良好调优，但冲突或高维数据可能需要更多哈希表或更长的哈希键，从而增加内存和延迟。像 Annoy (Approximate Nearest Neighbors Oh Yeah) 这样的算法，它使用随机投影树森林，平衡了 O(log n) 搜索和轻量级索引，适用于中等规模数据集。关键在于，虽然亚线性复杂度避免了精确搜索的过高成本，但“隐藏”因素——内存使用、预处理时间和距离计算开销——显著影响实际速度。
随着数据集的增长，ANN 算法的实际优势变得清晰。一个具有 O(n) 时间的暴力搜索方法可能在几毫秒内处理 10,000 个点，但在 1000 万个点时就会变得困难。相比之下，一个 O(log n) 的方法（如 HNSW），如果经过适当调优，即使在该规模下也能保持毫秒级的查询。然而，数据集维度和数据分布很重要。例如，LSH 在高度簇状数据上表现不佳，除非哈希经过仔细调整，而基于图的方法（如 HNSW）能更好地适应不同的密度。现代库（例如 FAISS、Annoy、hnswlib）使用量化或 SIMD 指令等技术优化这些算法，以降低时间复杂度中的常数。开发者应优先在自己的特定数据上进行基准测试：理论复杂度设定了预期，但实际速度取决于算法的假设与数据结构和实现效率的契合程度。