Algorithme de complexité temporelle non monotone

Question

Comme exercice de pensée, j'essaie de penser à un algorithme qui a une courbe de complexité non monotone. La seule chose à laquelle je pouvais penser était un algorithme avec une solution asymptotique dans les extrémités.

Y at-il un tel algorithme, qui a une courbe de complexité non monotone, qui ne repose pas sur l'approximation asymptotique?

Answer 1

Je ne sais pas ce que vous entendez par « approximation asymptotique », mais théoriquement, il est facile de construire de tels « algorithme » ...

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

Answer 2

Je ne pense pas qu'il y ait beaucoup (tout) algorithmes réels comme celui-ci, mais juste à côté du haut de ma tête, dans le code pseudo:

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

cet algorithme n'est pas asymptotique que n tend vers l'infini.

Answer 3

La transformée de Fourier discrète vient à l'esprit; si elle était appliquée comme suit, il serait non monotones (et discontinue):

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

depuis DFT fonctionne en O (N ** 2) et fonctionne fft en O (N log N).

En concevant un algorithme, on trouverait probablement un moyen de tamponner les données d'entrée pour supprimer un comportement non monotone (c'est-à-dire accélérer des entrées plus petites), comme cela est couramment fait avec fft.