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

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) );
}

Этот алгоритм не асимптотичен, так как n стремится к бесконечности.

Answer 3

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

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