Fonction qui est Big O (1) mais pas Ω (1)

Peut-on m'aider avec une fonction qui est Big O (1) mais pas Ω (1) et inversement? Certaines explications aideraient grandement.Fonction qui est Big O (1) mais pas Ω (1)

Source

2010-09-26 rda3mon

quand une fonction serait-elle O (1) mais pas Ω (1)? Pensez à ce que chacun veut dire. – aaronasterling

Puisque O (1) est une constante, il ne peut y avoir de fonction qui soit supérieure à O (1). C'est ce que je pense ... – rda3mon

Ceci est lié à http://stackoverflow.com/questions/3209139/is-the-time-complexity-of-the-empty-algorithm-o0 – andand

Big-O signifie < = et grand Omega signifie> =, donc une fonction qui est O (1) mais pas Omega (1) est f (n) = 1/n. Pour l'inverse, f (n) = n fonctionne.

Source

2010-09-26 17:48:40

@Keith: Comment pourriez-vous jamais construire un algorithme en prenant un nombre fractionnaire d'étapes? –

Vous ne pouvez pas. Mais ce n'était pas la question. –

Ensuite, est-ce une question valide en premier lieu? – rda3mon

Fonction qui est Big O (1) mais pas Ω (1)

Répondre

Questions connexes