Quelle est la «bonne» définition des limites supérieure et inférieure?

19

Soit le pire temps d'exécution d'un problème sur une entrée de taille n . Faisons un peu bizarre le problème en fixant f ( n ) = n 2 pour n = 2 k mais f ( n ) = n pour n = 2 kf(n)nf(n)=n2n=2kf(n)=n .n=2k+1

  1. Alors, quelle est la limite inférieure du problème? La façon dont je l'ai compris n'est que la borne inférieure de . Mais nous savons que f ( n ) = Ω ( n 2 ) implique qu'il existe une constante k , n 0 telle que pour tout n > n 0 , f ( n ) > k n 2 , ce qui n'est pas vrai. Il semble donc que l'on ne puisse dire que f ( n ) = Ω ( n )f(n)f(n)=Ω(n2)kn0n>n0F(n)>kn2f(n)=Ω(n). Mais généralement, nous appellerons le problème a une limite inférieure de , non?Ω(n2)

  2. En supposant que , ce qui signifie qu'il existe une constante k , n 0 telle que pour tout n > n 0 , g ( n ) > k n 2 . Supposons également qu'un problème ait le temps d'exécution g ( n ) . Si nous pouvons réduire ce problème pour tous les nombres premiers n à un autre problème (avec la même taille d'entrée), pouvons-nous dire que le temps d'exécution de l'autre problème a une borne inférieure de Ω ( ng(n)=Ω(n2)kn0n>n0g(n)>kn2g(n)n ?Ω(n2)

Wei Yu
la source
12
C'est pourquoi les mathématiciens utilisent lim sup et lim inf.
Peter Shor
1
Je pense donc que je comprends la différence. Je pense que les gens du poste comprendront juste Omega comme infiniment souvent. Mais au cas où je voudrais faire une distinction explicite, y a-t-il des notations que je peux utiliser autre que de l'étendre?
Wei Yu
3
@Wei Yu: lim sup et lim inf. Vous dites pour une constanteksi vous voulez dire queg(n)kn2infiniment souvent, et lim infg(n)
lim supg(n)n2k
kg(n)kn2si vous voulez direg(n)kn2pour toutnsuffisamment grand. Surtout si vous parlez à des mathématiciens.
lim infg(n)n2k
g(n)kn2n
 
Peter Shor
12
@Wei: Pour la plupart des théoriciens de la complexité (voir Lance ci-dessous), votre fonction est θ (n ^ 2); pour la plupart des algorithmistes (voir Knuth ou CLRS), votre fonction est Ο (n ^ 2) et Ω (n). Les deux notations sont presque, mais pas complètement, standard dans leurs sous-communautés; pour aggraver les choses, ces deux sous-communautés se chevauchent fortement! Donc, si la notation que vous utilisez est importante, vous devez dire explicitement quelle notation vous utilisez. (Heureusement, cela compte rarement.)
Jeffε
2
@Jeffe. Je pense que vous devriez poster votre commentaire comme réponse.
chazisop

Réponses:

13

La bonne définition de est qu'il existe certains k > 0 tels que pour infiniment n , f ( n ) k n 2 . La définition infiniment fréquente des limites inférieures gère vos problèmes et comment nous les utilisons dans la pratique.f(n)=Ω(n2)k>0nf(n)kn2

J'ai écrit un article à ce sujet en 2005.

Certains manuels ont cette bonne définition, d'autres non.

Lance Fortnow
la source
14
Knuth n'est pas d'accord avec vous: portal.acm.org/citation.cfm?id=1008329
Jeffε
4
CLRS et Wikipedia sont également en désaccord avec vous. La définition infinie-souvent est une alternative notable, mais semble être moins largement utilisée.
Anonyme
Je pense que ces définitions sont toutes d'accord lorsque l'ensemble des exceptions est la mesure 0.
Carter Tazio Schonwald
2
Le problème des définitions «infiniment souvent» est qu'elles n'excluent généralement pas «infiniment souvent non». Nous avons donc la conséquence horrible qu'avec cette définition, mais aussi f ( n ) = o ( n + 1 ) , où Ω et o sont censés être des ordres stricts dans un certain sens. Je n'aime vraiment pas ça. Au moins, la suggestion de @ Carter d'exceptions de mesure 0 est un peu moins horrible, tout en permettant un ordre plus fin que celui habituel. f(n)=Ω(n2) f(n)=o(n+1)Ωo
András Salamon
2
@Jukka: Non, je suis abusant ici. Comme vous l'indiquez, je dois corriger mon argument pour utiliser O au lieu de o . Permettez - moi de répéter donc l'objection réelle sans utiliser o ou O . Avec "infiniment souvent", on a l'anomalie que n = Ω ( f ( n ) ) , f ( n ) = Ω ( n 2 ) , pourtant n Ω ( n 2 ) . Donc Ω ne forme même pas de précommande.oOooOn=Ω(f(n))f(n)=Ω(n2)nΩ(n2)Ω
András Salamon
4

Avec la définition de Knuth , vous ne pouvez affirmer que . Comme vous le constatez, cela n'est pas intuitif et se produit pour les fonctions que Vitányi et Meertens appellent «sauvages». Ils proposent de définirf(n)Ω(n)

Ω(f(n))={gδ>0:n0>0:n>n0:g(n)δf(n)}.

(C'est la même chose que la définition de Lance.) Avec cette définition .f(n)Ω(n2)

Marcus Ritt
la source
2

Je ne connais pas le plus utilisé, mais je crois que je connais le plus ancien usage (pour l'informatique de toute façon).

Dans l'article de 1965 de Hartmanis & Stearns "Sur la complexité de calcul des algorithmes", le corollaire 2.1 est:

UTinfnT(n)U(n)0SUST

SKO(K(n))T(n)n/kknT(n)T(n+1) , mais il ne doit pas nécessairement être constructible dans le temps.

k=1 mais ne respecte pas la deuxième règle.

Corollary 2.2 is the reciproral of the above and uses limit supremum, but still has these requirements. I guess as algorithms got more complex by the years, it is possible that the requirements have been relaxed.

chazisop
la source
2

Je pense que nous devons distinguer deux choses:

  • une borne inférieure pour une fonction
  • une borne inférieure pour un problème (algorithme)

Pour les fonctions, lorsque nous fixons un ordre, la définition de limite inférieure / supérieure en découle. Si la relation d'ordre est une majorisation asymptotique (en ignorant les facteurs constants)

Fg:c,nm>n. F(X)cg(X)

alors la définition est la définition habituelle de O et Ω. Les deux sont largement utilisés dans d'autres domaines comme la combinatoire.

But when we talk about a lowerbound for a problem (an algorithm) what we really want to say is that the problem requires certain amount of resources (for running the algorithm solving the problem). Often the complexity classes are parametrized by functions like Time(t(n)), and we simple say that the problem is lower bounded by a function, but this only works for nice functions (e.g. the running time of the algorithm is monotone, etc.). What we want to say in these cases is that we need n2 running time to solve the problem, i.e. less than n2 running time is not sufficient, which formally becomes Lance's definition that the running time of the algorithm is not in o(t(n)).

Kaveh
la source