algorithm - 非单调时间复杂度算法

Question

作为一个思维练习，我正在尝试考虑一种具有非单调复杂度曲线的算法。我唯一能想到的是一些在四肢中具有渐近解的算法。

有没有这样一种算法，具有非单调的复杂度曲线，不依赖于渐近逼近？

Answer 1

想到离散傅里叶变换；如果按如下方式应用，它将是非单调的(并且是不连续的):

if is_power_of_2(len(data)):
    return fft(data)
return dft(data)

因为 dft 在 O(N**2) 中运行而 fft 在 O(N log N) 中运行。

设计算法时，人们可能会找到一种方法来填充输入数据以消除非单调行为(即加速较小的输入)，就像 fft 常用的那样。