In Anirban166/testComplexity: Asymptotic Complexity Testing Framework

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

Abstract

Being a reference implementation of the standard optimal partitioning algorithm in C, (using the square-error loss) the function opart::gaussian computes the optimal changepoint model for a vector of real-valued data and a non-negative real-valued penalty, given the square loss (to minimize) / gaussian likelihood (to maximize). Note that it is not available on CRAN (as far as I observed), and has to be fetched from the github repository.

Time complexity

The standard optimal partitioning algorithm is quadratic in time complexity, which means the resulting complexity of this algorithm (it being a reference implementation) is quadratic as well.

However, there are several ways to speed up the dynamic programming algorithms including the pruning of the solution space, and the algorithms which provide a faster (log-linear time) implementation of the same include:

• changepoint::cpt.mean, which provides cpt.mean and other functions which compute the optimal solution to the penalized problem via the PELT algorithm, which is log-linear time complexity. Please check this article for more information on the same, including complexity analysis for the PELT and SegNeigh algorithms.

• fpop::Fpop: computes the optimal solution to the penalized problem via the FPOP algorithm, which has log-linear time complexity as well. The article regarding FPOP can be found here.

Reference

Reference enacting as the source for me to extract the above information can be found here.

Testing

Using testComplexity functions we can verify the quadratic time complexity for this algorithm:

library(testComplexity)
df <- asymptoticTimings(opart::opart_gaussian(rnorm(N), 1), data.sizes = 10^seq(1, 4, by = 0.5), max.seconds = 0.1)
asymptoticTimeComplexityClass(df)
#> [1] "quadratic"

^{Created on 2020-08-17 by the reprex package (v0.3.0)}

Anirban166/testComplexity documentation built on Sept. 17, 2024, 11:06 a.m.