非单调时间复杂度算法

Question

作为一种思维练习，我试图想到具有非单调复杂度曲线的算法。我唯一能想到的是一些渐近式解决方案。

有没有这种算法，它有非单调复杂曲线，它不依赖于渐近逼近？

Answer 1

我不知道你说“渐近近似”的意思，但在理论上，它很容易建造这种“算法” ......

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

Answer 2

我不认为有很多（任何）真正的算法是这样的，但就在我的头顶，在伪代码：当n趋于无穷

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

这种算法是不渐进。

Answer 3

想到离散傅里叶变换;如果它被施加如下这将是非单调（和不连续的）：

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

因为为O DFT运行（N ** 2）和FFT运行在O（N日志N）。设计一个算法，人们可能会找到一种方法来填充输入数据以消除非单调行为（即加速较小的输入），就像通常用fft所做的那样。