Existe-t-il des algorithmes O (1 / n)?

Existe-t-il des algorithmes O (1 / n)?

Ou autre chose qui est inférieur à O (1)?

Cette question n'est pas aussi stupide que cela puisse paraître. Au moins théoriquement, quelque chose comme O (1 / n ) est tout à fait sensé lorsque nous prenons la définition mathématique de la notation Big O :

Maintenant, vous pouvez facilement remplacer g ( x ) par 1 / x … il est évident que la définition ci-dessus est toujours valable pour certains f .

Dans le but d'estimer la croissance asymptotique à l'exécution, cela est moins viable… un algorithme significatif ne peut pas aller plus vite à mesure que l'entrée augmente. Bien sûr, vous pouvez construire un algorithme arbitraire pour y parvenir, par exemple le suivant:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

De toute évidence, cette fonction passe moins de temps à mesure que la taille d'entrée augmente… au moins jusqu'à une certaine limite, imposée par le matériel (précision des nombres, minimum de temps qui sleeppeut attendre, temps pour traiter les arguments, etc.): cette limite serait alors un borne inférieure constante donc en fait la fonction ci-dessus a toujours le temps d'exécution O (1).

Mais il existe en fait des algorithmes du monde réel où le temps d'exécution peut diminuer (au moins partiellement) lorsque la taille d'entrée augmente. Notez cependant que ces algorithmes ne présenteront pas de comportement d'exécution inférieur à O (1). Pourtant, ils sont intéressants. Par exemple, prenez l'algorithme de recherche de texte très simple de Horspool . Ici, le temps d'exécution attendu diminuera à mesure que la longueur du modèle de recherche augmentera (mais l'augmentation de la longueur de la botte de foin augmentera à nouveau le temps d'exécution).

Oui.

Il existe précisément un algorithme à l'exécution O (1 / n), l'algorithme "vide".

Pour qu'un algorithme soit O (1 / n), cela signifie qu'il s'exécute asymptotiquement en moins d'étapes que l'algorithme composé d'une seule instruction. S'il s'exécute en moins d'étapes qu'une étape pour tout n> n0, il ne doit précisément contenir aucune instruction pour celles n. Étant donné que la vérification «si n> n0» coûte au moins 1 instruction, elle ne doit comprendre aucune instruction pour tous les n.

Pour résumer: le seul algorithme qui est O (1 / n) est l'algorithme vide, composé d' aucune instruction.

sharptooth est correct, O (1) est la meilleure performance possible. Cependant, cela n'implique pas une solution rapide, juste une solution à temps fixe.

Une variante intéressante, et peut-être ce qui est vraiment suggéré, est de savoir quels problèmes deviennent plus faciles à mesure que la population augmente. Je peux penser à 1 réponse, quoique artificielle et ironique:

Est-ce que deux personnes dans un ensemble ont le même anniversaire? Lorsque n dépasse 365, retourne vrai. Bien que pour moins de 365, c'est O (n ln n). Peut-être pas une bonne réponse car le problème ne devient pas plus facile mais devient simplement O (1) pour n> 365.

Ce n'est pas possible. La définition de Big-O n'est pas plus grande que l' inégalité:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

Donc, le B (n) est en fait la valeur maximale, donc si elle diminue à mesure que n augmente, l'estimation ne changera pas.

De mon apprentissage précédent de la grande notation O, même si vous avez besoin d'une étape (comme vérifier une variable, faire une affectation), c'est O (1).

Notez que O (1) est identique à O (6), car la "constante" n'a pas d'importance. C'est pourquoi nous disons que O (n) est identique à O (3n).

Donc, si vous avez besoin d'une seule étape, c'est O (1) ... et puisque votre programme a au moins besoin d'une étape, le minimum qu'un algorithme peut utiliser est O (1). A moins que si nous ne le faisons pas, alors c'est O (0), je pense? Si nous faisons quoi que ce soit, alors c'est O (1), et c'est le minimum que cela peut faire.

(Si nous choisissons de ne pas le faire, cela peut devenir une question Zen ou Tao ... dans le domaine de la programmation, O (1) est toujours le minimum).

Ou que diriez-vous de ceci:

programmeur : patron, j'ai trouvé un moyen de le faire en temps O (1)!
patron : pas besoin de le faire, nous sommes en faillite ce matin.
programmeur : oh alors, ça devient O (0).

Non, ce n'est pas possible:

Comme n tend vers l'infini en 1 / n, nous obtenons finalement 1 / (inf), qui est en fait 0.

Ainsi, la classe big-oh du problème serait O (0) avec un n massif, mais plus proche du temps constant avec un n faible. Ce n'est pas raisonnable, car la seule chose qui peut être faite plus rapidement que le temps constant est:

void nothing() {};

Et même cela est défendable!

Dès que vous exécutez une commande, vous êtes au moins dans O (1), donc non, nous ne pouvons pas avoir une classe O de grande taille (1 / n)!

Qu'en est-il de ne pas exécuter la fonction du tout (NOOP)? ou en utilisant une valeur fixe. Cela compte-t-il?

J'utilise souvent O (1 / n) pour décrire les probabilités qui diminuent au fur et à mesure que les entrées augmentent - par exemple, la probabilité qu'une bonne pièce remonte en queue sur les flips log2 (n) est O (1 / n).

O (1) signifie simplement "temps constant".

Lorsque vous ajoutez une sortie anticipée à une boucle [1], vous (en notation big-O) transformez un algorithme O (1) en O (n), mais en le rendant plus rapide.

L'astuce est en général l'algorithme à temps constant est le meilleur, et linéaire est meilleur qu'exponentiel, mais pour de petites quantités de n, l'algorithme exponentiel peut en fait être plus rapide.

1: en supposant une longueur de liste statique pour cet exemple

Pour tous ceux qui lisent cette question et souhaitent comprendre de quoi parle la conversation, cela peut aider:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |

Je crois que les algorithmes quantiques peuvent effectuer plusieurs calculs "à la fois" via la superposition ...

Je doute que ce soit une réponse utile.

beaucoup de gens ont eu la bonne réponse (Non) Voici une autre façon de le prouver: Pour avoir une fonction, vous devez l'appeler et vous devez renvoyer une réponse. Cela prend un certain temps constant. MÊME SI le reste du traitement a pris moins de temps pour des entrées plus importantes, l'impression de la réponse (qui peut être supposée être un seul bit) prend au moins un temps constant.

Si la solution existe, elle peut être préparée et accessible en temps constant = immédiatement. Par exemple, en utilisant une structure de données LIFO si vous savez que la requête de tri est pour l'ordre inverse. Ensuite, les données sont déjà triées, étant donné que le modèle approprié (LIFO) a été choisi.

Quels problèmes deviennent plus faciles avec l'augmentation de la population? Une réponse est une chose comme bittorrent où la vitesse de téléchargement est une fonction inverse du nombre de nœuds. Contrairement à une voiture, qui ralentit plus vous la chargez, un réseau de partage de fichiers comme bittorrent accélère plus de nœuds connectés.

Vous ne pouvez pas descendre en dessous de O (1), cependant O (k) où k est inférieur à N est possible. Nous les avons appelés algorithmes de temps sublinéaires . Dans certains problèmes, l'algorithme de temps sublinéaire ne peut donner que des solutions approximatives à un problème particulier. Cependant, parfois, une solution approximative est très bien, probablement parce que l'ensemble de données est trop volumineux, ou que c'est beaucoup trop coûteux en calcul pour tout calculer.

Et ça:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

à mesure que la taille de la liste augmente, le temps d'exécution attendu du programme diminue.

O (1 / n) n'est pas inférieur à O (1), cela signifie essentiellement que plus vous avez de données, plus l'algorithme va vite. Supposons que vous obtenez un tableau et remplissez-le toujours jusqu'à 10 ¹⁰⁰ éléments s'il en contient moins et ne faites rien s'il y en a plus. Celui-ci n'est pas O (1 / n) bien sûr mais quelque chose comme O (-n) :) Dommage que la notation O-big ne permette pas les valeurs négatives.

Comme cela a été souligné, à l'exception de l'exception possible de la fonction nulle, il ne peut y avoir de O(1/n)fonctions, car le temps nécessaire devra approcher de 0.

Bien sûr, il existe des algorithmes, comme celui défini par Konrad, qui semblent être inférieurs O(1)à au moins un certain sens.

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

Si vous souhaitez étudier ces algorithmes, vous devez soit définir votre propre mesure asymptotique, soit votre propre notion du temps. Par exemple, dans l'algorithme ci-dessus, je pourrais autoriser l'utilisation d'un certain nombre d'opérations "gratuites" un nombre de fois défini. Dans l'algorithme ci-dessus, si je définis t 'en excluant le temps pour tout sauf le sommeil, alors t' = 1 / n, qui est O (1 / n). Il y a probablement de meilleurs exemples, car le comportement asymptotique est trivial. En fait, je suis sûr que quelqu'un peut trouver des sens qui donnent des résultats non triviaux.

La plupart des autres réponses interprètent big-O comme étant exclusivement sur le temps d'exécution d'un algorithme. Mais comme la question ne le mentionnait pas, j'ai pensé qu'il valait la peine de mentionner l'autre application du big-O en analyse numérique, qui concerne l'erreur.

De nombreux algorithmes peuvent être O (h ^ p) ou O (n ^ {- p}) selon que vous parlez de taille de pas (h) ou de nombre de divisions (n). Par exemple, dans la méthode d'Euler , vous recherchez une estimation de y (h) étant donné que vous connaissez y (0) et dy / dx (la dérivée de y). Votre estimation de y (h) est d'autant plus précise que h se rapproche de 0. Ainsi, pour trouver y (x) pour des x arbitraires, on prend l'intervalle de 0 à x, on le divise jusqu'à n morceaux et on exécute la méthode d'Euler à chaque point, pour passer de y (0) à y (x / n) à y (2x / n), etc.

La méthode d'Euler est donc un algorithme O (h) ou O (1 / n), où h est généralement interprété comme une taille de pas et n est interprété comme le nombre de fois que vous divisez un intervalle.

Vous pouvez également avoir O (1 / h) dans de vraies applications d'analyse numérique, en raison d' erreurs d'arrondi à virgule flottante . Plus votre intervalle est petit, plus l'annulation se produit pour la mise en œuvre de certains algorithmes, plus la perte de chiffres significatifs, et donc plus d'erreurs, qui se propagent à travers l'algorithme.

Pour la méthode d'Euler, si vous utilisez des virgules flottantes, utilisez un pas et une annulation suffisamment petits et vous ajoutez un petit nombre à un grand nombre, en laissant le grand nombre inchangé. Pour les algorithmes qui calculent la dérivée en soustrayant l'un de l'autre deux nombres d'une fonction évaluée à deux positions très proches, approximant y '(x) avec (y (x + h) - y (x) / h), dans les fonctions lisses y (x + h) se rapproche de y (x), ce qui entraîne une annulation importante et une estimation du dérivé avec moins de chiffres significatifs. Cela se propagera à son tour à l'algorithme pour lequel vous avez besoin de la dérivée (par exemple, un problème de valeur limite).

OK, j'y ai réfléchi un peu, et peut-être existe-t-il un algorithme qui pourrait suivre cette forme générale:

Vous devez calculer le problème du vendeur itinérant pour un graphique de 1000 nœuds, mais vous obtenez également une liste de nœuds que vous ne pouvez pas visiter. À mesure que la liste des nœuds invisibles s'allonge, le problème devient plus facile à résoudre.

Je vois un algorithme qui est O (1 / n) certes à une limite supérieure:

Vous avez une grande série d'entrées qui changent en raison de quelque chose d'extérieur à la routine (peut-être qu'elles reflètent le matériel ou cela pourrait même être un autre cœur du processeur qui le fait.) Et vous devez sélectionner une aléatoire mais valide.

Maintenant, si cela ne changeait pas, il vous suffirait de faire une liste d'articles, d'en choisir un au hasard et d'obtenir O (1) fois. Cependant, la nature dynamique des données empêche de faire une liste, vous devez simplement sonder au hasard et tester la validité de la sonde. (Et notez qu'intrinsèquement, il n'y a aucune garantie que la réponse est toujours valide lorsqu'elle est retournée. Cela pourrait encore avoir des utilités - disons, l'IA d'une unité dans un jeu. Elle pourrait tirer sur une cible qui est tombée hors de vue alors qu'elle était tirant sur la détente.)

Cela a une performance de l'infini dans le pire des cas, mais une performance de cas moyenne qui diminue à mesure que l'espace de données se remplit.

En analyse numérique, les algorithmes d'approximation devraient avoir une complexité asymptotique sous-constante dans la tolérance d'approximation.

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

Je suppose que moins de O (1) n'est pas possible. Tout temps pris par algo est appelé O (1). Mais pour O (1 / n) que diriez-vous de la fonction ci-dessous. (Je sais qu'il existe de nombreuses variantes déjà présentées dans cette solution, mais je suppose qu'elles ont toutes quelques défauts (pas majeurs, elles expliquent bien le concept). En voici une, juste pour les besoins de l'argument:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Ainsi, à mesure que n augmente, la fonction prendra de moins en moins de temps. De plus, il est garanti que si l'entrée est réellement 0, la fonction prendra une éternité pour revenir.

On pourrait dire qu'il sera limité par la précision de la machine. ainsi sinc eit a une borne supérieure c'est O (1). Mais nous pouvons également contourner cela, en prenant les entrées de n et C dans la chaîne. Et l'addition et la comparaison se font sur chaîne. L'idée est que, avec cela, nous pouvons réduire n arbitrairement petit. Ainsi, la limite supérieure de la fonction n'est pas bornée, même lorsque nous ignorons n = 0.

Je crois également que nous ne pouvons pas simplement dire que le temps d'exécution est O (1 / n). Mais nous devrions dire quelque chose comme O (1 + 1 / n)

Il peut être possible de construire un algorithme qui est O (1 / n). Un exemple serait une boucle qui itère un multiple de f (n) -n fois où f (n) est une fonction dont la valeur est garantie supérieure à n et la limite de f (n) -n lorsque n approche de l'infini est zéro. Le calcul de f (n) devrait également être constant pour tout n. Je ne sais pas à quoi ressemblerait f (n) ni quelle application aurait un tel algorithme, à mon avis cependant une telle fonction pourrait exister mais l'algorithme résultant n'aurait d'autre but que de prouver la possibilité d'un algorithme avec O (1 / n).

Je ne connais pas les algorithmes mais des complexités inférieures à O (1) apparaissent dans les algorithmes randomisés. En fait, o (1) (petit o) est inférieur à O (1). Ce type de complexité apparaît généralement dans les algorithmes randomisés. Par exemple, comme vous l'avez dit, lorsque la probabilité d'un événement est d'ordre 1 / n, ils la désignent par o (1). Ou quand ils veulent dire que quelque chose se produit avec une probabilité élevée (par exemple 1 - 1 / n), ils le notent avec 1 - o (1).

Si la réponse est la même quelles que soient les données d'entrée, vous disposez d'un algorithme O (0).

ou en d'autres termes - la réponse est connue avant la soumission des données d'entrée - la fonction pourrait être optimisée - donc O (0)

La notation Big-O représente le pire scénario pour un algorithme qui n'est pas la même chose que son temps d'exécution typique. Il est simple de prouver qu'un algorithme O (1 / n) est un algorithme O (1). Par définition,
O (1 / n) -> T (n) <= 1 / n, pour tout n> = C> 0
O (1 / n) -> T (n) <= 1 / C, puisque 1 / n <= 1 / C pour tout n> = C
O (1 / n) -> O (1), car la notation Big-O ignore les constantes (c'est-à-dire que la valeur de C n'a pas d'importance)

Rien n'est plus petit que O (1) La notation Big-O implique le plus grand ordre de complexité pour un algorithme

Si un algorithme a un temps d'exécution de n ^ 3 + n ^ 2 + n + 5, alors il est O (n ^ 3) Les puissances inférieures n'ont pas d'importance ici car n -> Inf, n ^ 2 ne sera pas pertinent par rapport à n ^ 3

De même que n -> Inf, O (1 / n) ne sera pas pertinent par rapport à O (1) donc 3 + O (1 / n) sera le même que O (1) faisant ainsi de O (1) le plus petit calcul possible complexité

inline void O0Algorithm() {}

Voici un algorithme simple O (1 / n). Et ça fait même quelque chose d'intéressant!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O (1 / n) est possible car il décrit comment la sortie d'une fonction change en fonction de la taille croissante de l'entrée. Si nous utilisons la fonction 1 / n pour décrire le nombre d'instructions qu'une fonction exécute, il n'est pas nécessaire que la fonction prenne zéro instruction pour n'importe quelle taille d'entrée. C'est plutôt que pour chaque taille d'entrée, n au-dessus d'un certain seuil, le nombre d'instructions requises est limité au-dessus par une constante positive multipliée par 1 / n. Comme il n'y a pas de nombre réel pour lequel 1 / n est 0 et la constante est positive, il n'y a aucune raison pour que la fonction soit contrainte de prendre 0 ou moins d'instructions.