非单调时间复杂度算法

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 通常所做的那样。

Answer 2

我不知道你所说的“渐近逼近”是什么意思，但从理论上讲，构建这样的“算法”很容易......

var l = non_monotonic_function(input.size);
for (var i = 0; i < l; ++ i)
   do_some_O1_stuff(i);

Answer 3

我不认为有很多（任何？）像这样的真实算法，但就在我的脑海中，在伪代码中：

void non_monotonic_function(int n)
{
    System.wait( Math.sin(n) );
}

这个算法不是渐近的，因为 n 趋于无穷大。