分析二分分割算法在有限数据下的复杂度，给出实际运行快慢的理论依据。
Finite Sample Complexity Analysis of Binary Segmentation
- 通过新算法计算二分分割在给定参数下的最好与最坏情况分裂次数
- 构造出能实现最优和最差性能的合成数据，用于验证算法正确性
- 实测表明该算法在实际中通常接近最优速度，适合工程部署
二分分割是一种经典的贪心算法，通过递归划分序列数据来检测变化点或构建决策树。理论上其时间复杂度最坏为 $O(NK)$，最好为 $O(N\log K)$，其中 $N$ 为数据量，$K$ 为预期分割数。本文针对有限 $N$、$K$ 及最小段长参数，提出新方法分析二分分割的时间与空间复杂度。首先，设计算法计算该算法必须考虑的最佳与最坏情况分裂次数；其次，构造可实现最佳与最差情形的合成数据，用于测试算法实现正确性；最后，基于真实数据的实证分析表明，二分分割在实践中通常接近最优运行速度。
原文摘要 · Abstract (English)
Binary segmentation is the classic greedy algorithm which recursively splits a sequential data set by optimizing some loss or likelihood function. Binary segmentation is widely used for changepoint detection in data sets measured over space or time, and as a sub-routine for decision tree learning. In theory it should be extremely fast for $N$ data and $K$ splits, $O(N K)$ in the worst case, and $O(N \log K)$ in the best case. In this paper we describe new methods for analyzing the time and space complexity of binary segmentation for a given finite $N$, $K$, and minimum segment length parameter. First, we describe algorithms that can be used to compute the best and worst case number of splits the algorithm must consider. Second, we describe synthetic data that achieve the best and worst case and which can be used to test for correct implementation of the algorithm. Finally, we provide an empirical analysis of real data which suggests that binary segmentation is often close to optimal speed in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。