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

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

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

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

Этот алгоритм не являетсян уходит в бесконечность.

Answer 3

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

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