enter image description here

Oto stwierdza to T (n) jest o (n ^ 4). Ale chcę wiedzieć, dlaczego nie jest o (n ^ 3)? Zawiera n ^ 3, a jeśli pominęmy 20N i 1, powinno być O (n ^ 3), a nie o (n ^ 4). Dlaczego tak jest?

0
igelr 27 luty 2019, 21:54

2 odpowiedzi

Najlepsza odpowiedź

Jest w O (n ^ 3), ale O (n ^ 4), O (n ^ 5) itp. Jest superset o (n ^ 3), więc jeśli coś jest w O (n ^ 3), to może być również w O (n ^ 100). Najlepsza odpowiedź i ta używana przez konwencję jest najmniejsza, do której należy, do której należy o (n ^ 3), ale nie jest to jedyny.

1
Jon Doe 28 luty 2019, 00:45

Myślę, że jesteś zdezorientowany między notatą THETA i Notation Big O.

Notacja THETA określa szorstki oszacowanie czasu pracy algorytmu, podczas gdy Big O Notation określa najgorszy czas pracy algorytmu.

Metoda, o której wspomniana powyżej jest używana do obliczenia teta, a nie Big O. Duży o wyżej wymienionym problemie może być O (n ^ 4), O (n ^ 5), O (n ^ 6) i tak dalej ... Wszystkie są poprawne wartości. Ale dla Teta, tylko THETA (N ^ 3) jest poprawna.

1
Akash Chandwani 27 luty 2019, 19:10