Complexitate

[•soriyn]

Am si eu o intrebare. Cam cum ti-ai putea da seama daca o anume complexitate se incadreaza in limita de timp ? Adica se poate face o estimare de genul : cam pentru ce N se incadreaza O(N^3) in 0,2 sec ?

[•MciprianM]

Poti sa iti iei o limita superioara de "numar de instructiuni pe secunda". Citeam pe forumul infoarena, ca 60 de milioane de "instructiuni pe secunda" e o limita superioara buna. La 0.2 secunde ar veni 12 milioane. Pentru n 250, n^3 = 15 milioane si ceva. In functie de cat de complexe sunt "instructiunile" tale, s-ar putea sa mearga si n 300, 350 pentru instructiuni foarte simple si o constanta subunitara relativ mica (1/3, 1/6 ...) sau s-ar putea sa iti depaseasca limita de timp si cu n 150, daca instructiunile sunt complexe (de exemplu n^3 impartiri).
In principiu te-ai putea orienta asa - desi nu merge intotdeauna (limita de timp o secunda):
n^4:  n <= 80
n^3:  n <= 400
n^2 log n:  n <= 2500
n^2:  n <= 7000
n logn:  n <= 2000000
n     :  n <= 50000000
log n : n <= 2^50000000
sqrt (n) :  n <= 10^16

[•soriyn]

Sunt constient ca e relativa treaba asta. Ce ma interesa era sa imi fac o idee, ceva orientativ. Multumesc.