Dupliqué possible:
y a-t-il des algorithmes O (1 / N)?Cela vient d'apparaître dans ma tête sans raison particulière, et je suppose que c'est une question étrange. Existe-t-il des algorithmes ou des problèmes connus qui obtiennent réellement plus facile ou plus vite pour résoudre avec une plus grande entrée? Je suppose que s'il y en a, cela ne serait pas pour des choses comme des mutations ou du tri, ce serait pour des problèmes de décision. Peut-être qu'il y a un problème où avoir une tonne d'entrée permet de décider quelque chose, mais je ne peux pas imaginer quoi.
S'il n'y a pas de complexité négative, y a-t-il une preuve qu'il ne peut y avoir? Ou est-ce que personne ne l'ait encore trouvé?
7 Réponses :
Pas vraiment. O (1) est le meilleur que vous puissiez espérer.
Le plus proche que je puisse penser à la traduction linguistique, qui utilise de grands ensembles de données de phrases dans la langue cible pour correspondre à des extraits plus petits de la langue source. Plus le jeu de données est grand, meilleur (et dans une certaine mesure plus rapide) de la traduction. Mais ce n'est toujours pas même O (1).
Je pense aussi que c'est le mauvais "n". Ne serait pas le nombre d'extraits? Vous les traduisez, pas le jeu de données, qui vous donnerait O (n) ou pire.
Celui qui obtiendrait vraiment la tête des gens à filer ... est un noop o (1) ou o (0)?
@Briangideon Je pense que cela dépend (à la fois sur l'affaire et vos définitions). Si avant le noop, vous avez eu une commande qui nécessite d'attendre 1 horloge avant d'exécuter la commande suivante (vous devez donc mettre un sommet entre eux), vous pourriez alors affirmer que le temps nécessaire à la lecture et à exécuter le noop est en réalité du temps de la commande précédente (ou suivante) (mais cela dépend de votre définition du temps d'une commande), dans ce cas, vous pourriez dire que c'est O (0) puisque elle n'ajoute pas de temps au programme. Toutefois, si vous ajoutez un noop inutile, il ajoute du temps au programme et prend le (1).
Comme indiqué dans la réponse acceptée ici, il existe aucun algorithme de travail plus rapide avec une plus grande entrée.
y a-t-il des algorithmes O (1 / N)?
Même un algorithme comme En particulier, l'auteur fait référence à un algorithme de recherche de substration relativement simple: ps mais en utilisant le terme «complexité négative» pour de tels algorithmes ne semble pas être raisonnable pour moi. dormir (1 / N) doit passer du temps à lire son entrée, de sorte que son temps d'exécution a une borne inférieure.
http://en.wikipedia.org/wiki/horspool
Comme la réponse acceptée, il a finalement été acquitté, il sont NO O (1 / N) algorithmes. Le temps d'exécution peut diminuer jusqu'à un peu fini n, mais asymptotiquement, il ne peut pas être O (1).
Mais même ici O (1 / N) n'est pas négatif. Néanmoins le fait que la définition formelle contrainte Big-Oh d'être positive.
@Shreevatsar pourquoi vous me dites cela? Dans mon message, je ne prétends pas ces algorithmes d'être o (rien).
Je ne trouve pas quoi que ce soit sur les pages wiki faisant la prétention que c'est mieux que O (n) et la réponse que vous connaissez bien clairement: "Notez que ces algorithmes ne présenteront pas le comportement d'exécution ci-dessous. (1)".
Je souligne qu'il n'y a pas d'algorithmes qui n'obtiennent pas toujours plus rapidement avec une entrée plus grande. Jusqu'à une certaine taille d'entrée, oui.
@Shreeevatsar Toute algorithme est un sujet à des limitations matérielles et nous ne les discutons pas ici. Et en dehors de cela, l'algorithme "sommeil (1000 / N)" semble être un exemple suffisant pour moi.
@paxdiablo j'ai mis à jour mon message pour répondre à de telles questions :) (Même si l'article original les a adressé aussi)
@Nikita: Bon lien vers la chose O (1 / N) au fait. En fait, je pense que c'est plus intéressant que cette question. Cependant, je ne dis pas que cette question n'est pas intéressante.
@Brian à ce que je suis d'accord, il n'y a pas grand chose à discuter de la question «peut-être qu'une tâche nécessite un temps négatif» :)
Non! Même théoriquement (rien à voir avec les limitations matérielles), un algorithme comme sommeil (1 / N) doit prendre du temps ε + 1 / N, car il doit lire l'entrée au moins. (En fait, au moins O (log n) pour lire l'entrée elle-même.)
Eh bien, pour de nombreux calculs comme "Entrée donnée A Retour F (A)" Vous pouvez "cache" des résultats de calcul (en stockez-les dans la matrice ou la carte), ce qui rendra le calcul plus rapidement avec un plus grand nombre de valeurs, si certaines de ces valeurs. Valeurs répétez.
Mais je ne pense pas que cela qualifie de "complexité négative". Dans ce cas, les performances les plus rapides compteront probablement comme O (1), le pire des performances des cas seront O (n) et la performance moyenne sera quelque part entre cela.
Ceci est un peu applicable pour le tri des algorithmes - certains d'entre eux ont une complexité du scénario et une complexité du pire des cas (n ^ 2), en fonction de l'état des données à être trié.
Je pense que pour avoir une complexité négative, l'algorithme doit renvoyer le résultat avant qu'il ait été demandé de calculer le résultat. C'est à dire. Il devrait être connecté à une machine de temps et devrait être en mesure de traiter avec correspondant "Grandfather Paradox" .
Il y a en fait un nom pour ce type de programmation, des programmes qui finissent avant de commencer. J'aimerais pouvoir me souvenir de ce que ce nom est!
Non ce n'est pas possible. Étant donné que BIG-OH est supposé être une approximation du nombre d'opérations qu'un algorithme est lié à sa taille de domaine, il n'aurait aucun sens de décrire un algorithme comme un nombre négatif d'opérations.
La section de définition formelle du Wikipedia Article définit réellement la notation Big-Oh en termes de en utilisant des nombres réels positifs. Il n'y a donc même pas une preuve parce que tout le concept de Big-OH n'a aucune signification sur les nombres réels négatifs par la définition formelle.
Pour penser dans un algorithme qui s'exécute dans le temps négatif, est la même chose que penser à du temps à l'envers.
Si le programme commence à exécuter à 10h30 et s'arrête à 10h00 sans passer à 11h00, il vient d'exécuter avec le temps = O (-1).
=]
Maintenant, pour la partie mathématique:
Si vous ne pouvez pas trouver une séquence d'actions exécutées à l'envers (vous ne savez jamais ... lol) , la preuve est assez simple:
positivetime = o (-1) signifie:
Positivetime <= C * -1, pour tout C> 0 et N> N0> 0
Considérez la restriction «C> 0».
Nous ne pouvons pas trouver un nombre positif multiplié par -1 entraînera un autre nombre positif.
En prenant cela en compte, c'est le résultat:
Positivetime <= Negatishenviorumber, pour tout N> N0> 0
wich vient de prouver que vous ne pouvez pas avoir un algorithme avec O (-1).
Comme avec l'autre question sur l'algorithme vide, cette question est une question de définition plutôt que de savoir ce qui est possible ou impossible. Il est certainement possible de penser à un modèle de coût pour lequel un algorithme prend une heure (1 / N). (Ce n'est pas négatif, bien sûr, mais plutôt diminuer avec une entrée plus grande.) L'algorithme peut faire quelque chose comme D'autre part, la définition la plus simple et la plus standard de complexité de temps utilise des étapes temporelles unitaires. Il est impossible pour une fonction positive et valorisée d'avoir une asymptotique décroissante; le plus petit que cela puisse être est O (1). dormir (1 / N) comme l'une des autres réponses suggérées. Il est vrai que le modèle de coût décompose comme n est envoyé à l'infini, mais n jamais envoyé à l'infini; Chaque modèle de coût décompose éventuellement de toute façon. Dire que dormir (1 / n) prend du temps O (1 / N) peut être très raisonnable pour une taille d'entrée allant de 1 octet à 1 gigaoctet. C'est une très large gamme pour une formule de complexité de temps pour être applicable.
Je ne sais pas si cela vous convient tout à fait, mais cela me rappelle BitTorrent. Plus les gens téléchargent un fichier, plus il est plus rapide pour tous
Ce ne serait pas «négatif», ce serait exponentiel (ou autrement). O (n ^ -1) par exemple.
Il est possible (bien que peu probable IMO) qu'un effet d'enchevêtrement quantique étrange puisse conduire à un ordinateur qui produise ses résultats avant la réception de l'entrée. Cela serait-il qualifié de complexité négative ??
Ils devraient nous donner un nouveau badge pour ce fil. Quelque chose comme "Time-Travel" serait gentil ... lol. =]
Ce serait juste o (1). Votez pour ouvrir une liste de questions la plus drôle.
Merci pour la correction de la complexité inverse. J'étais très bête quand j'ai dit négatif. Suis-je me moqué d'ici?
@Tesserex: En fait, j'ai pensé que c'était une question intéressante. Au fait, je ne vois pas comment il s'agit d'un duplicata de la question citée. Tout le monde veut prendre un coup de poignard pour affirmer que O (1 / N) est le même concept que -O (n) par exemple?
@Tesserex: En outre, j'espère que vous ne pensez pas que je me moquais de s'amuser lorsque vous mentionnez la chose enchevêtrement quantique ... J'étais en fait d'être à moitié grave. Quoi ... le monde quantique est étrange!
Non, je voulais dire le commentaire la plus drôle de la question. Et je pense que je voulais dire 1 / N, pas négatif n. La vraie question était "plus rapide avec une plus grande entrée".
@Tessex: S'il vous plaît, ne vous méprenez pas. J'avais "complexité d'algorithme" cette année au collège, et c'était une excellente question au point de vue de mon élève. =]
Ce n'est pas une question en double. L'un est un sous-ensemble de l'autre.