Je suis vraiment confus au sujet du temps

Question

Je complexités comprends que le temps d'un algorithme T(n) peut être limitée par O(g(n)) par la définition:

T(n) is O(g(n)) iff there is a c > 0, n0 > 0, such that for all n >= n0: 

pour chaque entrée de la taille n, A prend au plus c * g(n) étapes. T(n) est le temps le plus long de toutes les entrées de taille n.

Cependant, ce que je ne comprends pas est la définition de Ω(g(n)). La définition est que pour certains entrée de taille n, A prend au moins c * g(n) étapes.

Mais si c'est la définition pour Ω alors je ne pourrais pas trouver une limite inférieure pour tout algorthm qui est la même que la limite supérieure? Par exemple, si le tri prend dans le pire des cas O(nlogn) alors ne serais-je pas en mesure de montrer facilement Ω(nlogn) ainsi que comment il doit y avoir au moins une mauvaise entrée pour toute taille n qui prendrait nlogn étapes? Supposons que nous parlons de heapsort. Je ne suis pas vraiment sûr de ce qui me manque ici parce que chaque fois que l'on m'apprend un nouvel algorithme, le temps pour une certaine méthode est soit Ɵ(g(n)) or O(g(n)), mais aucune explication n'est fournie pour savoir pourquoi c'est Ɵ or O.

J'espère que ce que j'ai dit était assez clair sinon demandez à ce que vous avez mal compris. J'ai vraiment besoin de cette confusion éclaircie. Je vous remercie.

Answer 1

La définition que je connais est que T (n) est Ω (g (n)) si pour une n0, pour tous n>n0, T(n) >= g(n)*k pour certains k.

Ensuite, quelque chose est Θ (n) si c'est à la fois O (g (n)) et Ω (g (n)).

Answer 2

O est une limite supérieure, ce qui signifie que nous connaissons un algorithme qui O(n lg n) prend, asymptotiquement, au plus une fois constants n lg n étapes dans le pire des cas.

Ω est une borne inférieure, ce qui signifie que nous savons qu'il est impossible pour un algorithme Ω(n lg n) de prendre asymptotiquement moins d'un n lg n pas dans le pire des cas. nous savons par exemple, si un algorithme est Ɵ(n lg n) alors à la fois, il est à la fois O(n lg n) (il en est au moins aussi vite que n lg n) et Ω(n lg n) (donc nous savons qu'il n'y a pas plus rapide que n lg n):

Ɵ est une limite étanche.

La raison pour laquelle votre argument est erroné est que vous supposez que vous connaissez Ɵ(n lg n), et pas seulement O(n lg n). Par exemple, nous savons qu'il existe un lien général Ω(n lg n) sur les tris de comparaison. Une fois que nous avons prouvé O(n lg n) pour mergesort, cela signifie donc que mergesort est Ɵ(n lg n). Notez que mergesort est aussiO(n^2), parce que c'est pas plus lent que n^2. (Ce n'est pas ainsi que les gens le décriraient, mais c'est ce que la notation formelle signifie.

Pour certains algorithmes, nous ne connaissons pas les limites strictes; le général 3SUM problem dans les modèles simples de calcul est connu pour être Ω(n lg n) parce qu'il peut être utilisé pour effectuer le tri, mais nous avons seulement Ɵ(n^2) algorithmes. Le meilleur algorithme pour le problème est entre n lg n et n^2; nous pouvons dire que c'est O(n^2) et Ω(n lg n), mais nous ne connaissons pas le Ɵ.

Il ya aussi o(f), ce qui signifie strictement inférieur à f, et ω(f), ce qui signifie strictement supérieur à f.