Алгоритм немонотонной временной сложности

Question

Как мысленное упражнение, я пытаюсь думать об алгоритме, который имеет немонотонную кривую сложности. Единственное, что я мог придумать, это какой-то алгоритм с асимптотическим решением в конечностях.

Есть ли такой алгоритм, который имеет кривую немонотонной сложности, которая не полагается на асимптотическое приближение?

Answer 1

Я не знаю, что вы имеете в виду под «асимптотическим приближением», но теоретически, легко построить такой «алгоритм» ...

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

Answer 2

Я не думаю, что есть много (любой) реальные алгоритмы, как это, но в непосредственной близости от верхней части головы, в псевдокоде:

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) 

, так как DFT работает в O (N ** 2) и FFT работает в O (N журнал N).

При разработке алгоритма можно было бы найти способ для ввода входных данных для удаления немонотонного поведения (т. Е. Ускорения меньших входных данных), как это обычно делается с помощью fft.