|
Titlul: Complexitate Scris de: Sorin Rita din Decembrie 20, 2011, 22:11:13 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 ?
Titlul: Răspuns: Complexitate Scris de: MciprianM din Decembrie 20, 2011, 23:17:01 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 Titlul: Răspuns: Complexitate Scris de: Sorin Rita din Decembrie 20, 2011, 23:33:55 Sunt constient ca e relativa treaba asta. Ce ma interesa era sa imi fac o idee, ceva orientativ. Multumesc.
|