•Adix
Strain
Karma: -9
Deconectat
Mesaje: 44
|
|
« : Februarie 24, 2007, 19:20:24 » |
|
Ma uit peste forumul arhivei de probleme si vad la fiecare topic : "Problema se rezolva folosind o complexitate O(...) " . Cam banuiesc eu la ce se refera complexitatea respectiva , dar cum se calculeaza ? .. va rog help
|
|
|
Memorat
|
|
|
|
•peanutz
|
|
« Răspunde #1 : Februarie 24, 2007, 19:40:35 » |
|
In functie de structurile repetitive... Daca ai un for care merge de la 1 la n, instructiunile din cadrul for-urului se repeta de n ori, si complexitatea e liniara sau O(n)... Daca ai 2 structuri repetitive imbricate ceva in genul: for(i = 1; i <= n; ++i) for(j = 1; j <= n; ++j) { instr1; instr2; } Complexitatea este O(n^2).... La fel pentru 3 structuri, 4 etc O chestie ce mi se pare si mie ciudata este ca daca ai 3 structuri repetive fiecare de complexitate O(n), complexitatea finala este O(n) + O(n) + O(n).... care nu va fi egala cu 3*O(n), ci O(n) Later edit: Daca nu contine structuri repetitive complexitatea va fi O(1).
|
|
« Ultima modificare: Februarie 24, 2007, 19:45:07 de către Andrei Homorodean »
|
Memorat
|
....staind....
|
|
|
•Adix
Strain
Karma: -9
Deconectat
Mesaje: 44
|
|
« Răspunde #2 : Februarie 24, 2007, 19:43:35 » |
|
Mersi pt raspunsul rapid , dar am vazut tot felu de complexitati ciudate cu logaritmi si chestii de gen .. alea la ce se refera ?
|
|
|
Memorat
|
|
|
|
•peanutz
|
|
« Răspunde #3 : Februarie 24, 2007, 19:50:43 » |
|
Daca ai facut la (for-urile precendente:D)o optimizare: for(i = 1; i <= n && ok; ++i) for(j = 1; j <= n; ++j) { if(conditie) ok = 0; instr1; } La un anumit pas, ok poate sa devina 0... si instructiunile nu se vor executa de n*n, ci de n*logn...... Asta e explicatia gasita de mine si un exemplu
|
|
|
Memorat
|
....staind....
|
|
|
•cos_min
|
|
« Răspunde #4 : Februarie 24, 2007, 19:53:56 » |
|
spre ex daca ai :
for ( i = 1 , i <= n; i++ ) { for ( j = 1; j*j <= n; j++ ) { // ... } }
acesta are complexitatea O(n*logn);
|
|
|
Memorat
|
vid...
|
|
|
•CezarMocan
|
|
« Răspunde #5 : Februarie 24, 2007, 19:55:56 » |
|
Asta nu ii O(n*sqrt(n))??
|
|
|
Memorat
|
|
|
|
•Adix
Strain
Karma: -9
Deconectat
Mesaje: 44
|
|
« Răspunde #6 : Februarie 24, 2007, 20:00:19 » |
|
spre ex daca ai :
for ( i = 1 , i <= n; i++ ) { for ( j = 1; j*j <= n; j++ ) { // ... } }
acesta are complexitatea O(n*logn);
asta seamana mai degraba cu O(n*radical(n)) si la exemplul lui Andrei, de unde stim noi ca conditia respectiva se va rula vreodata , de ex, daca nu se ruleaza niciodata tot (n^2) ii
|
|
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #7 : Februarie 24, 2007, 20:03:37 » |
|
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #8 : Februarie 24, 2007, 20:04:51 » |
|
depinde de conditie. Nu e tocmai un exemplu f bun. uite un exemplu bun in n log n for (i=1;i<=n;i++) for (j=1;j<=n;j * =2) // instructiune
|
|
|
Memorat
|
|
|
|
•CezarMocan
|
|
« Răspunde #9 : Februarie 24, 2007, 20:05:56 » |
|
Gasesti si in Cormen o gramada de chestii despre toate chestiile astea care exprima numarul de pasi, de operatii, etc. (mai pe la inceput parca )
|
|
|
Memorat
|
|
|
|
•Adix
Strain
Karma: -9
Deconectat
Mesaje: 44
|
|
« Răspunde #10 : Februarie 24, 2007, 20:14:48 » |
|
M-ati mai lamurit putin. Am cautat si eu pe wikipedia dar mare lucru n-am inteles Mai is inca cateva chestii care mi-s neclare dar o sa le prind din zbor mersi
|
|
|
Memorat
|
|
|
|
•Tabara
|
|
« Răspunde #11 : Februarie 24, 2007, 20:16:15 » |
|
Sau in Tudor Sorin de a X-a exista un capitol special despre exprimarea complexitatii algoritmilor..
|
|
|
Memorat
|
|
|
|
•Adix
Strain
Karma: -9
Deconectat
Mesaje: 44
|
|
« Răspunde #12 : Februarie 24, 2007, 20:22:27 » |
|
Sau in Tudor Sorin de a X-a exista un capitol special despre exprimarea complexitatii algoritmilor.. Asta-i manual ? .. mentionez ca din clasa a 9-a si pana acum(clasa a 12-a) n-am avut nici un manual la info
|
|
« Ultima modificare: Februarie 24, 2007, 20:26:11 de către Suciu Adrian »
|
Memorat
|
|
|
|
•Darth_Niculus
|
|
« Răspunde #13 : Februarie 24, 2007, 20:29:15 » |
|
Sau in Tudor Sorin de a X-a exista un capitol special despre exprimarea complexitatii algoritmilor.. Asta-i manual ? .. mentionez ca din clasa a 9-a si pana acum(clasa a 12-a) n-am avut nici un manual la info Se gasesc in librarii.....
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #14 : Februarie 24, 2007, 21:07:48 » |
|
spre ex daca ai :
for ( i = 1 , i <= n; i++ ) { for ( j = 1; j*j <= n; j++ ) { // ... } }
acesta are complexitatea O(n*logn);
Scuze asta ii n*radical(n) , my bad
|
|
|
Memorat
|
vid...
|
|
|
•Tabara
|
|
« Răspunde #15 : Februarie 24, 2007, 21:12:08 » |
|
Poti sa faci comanda la editura ls-format. email: [email protected]web: www.ls-infomat.ro( Numai ca din cate stiu se pot face comenzi de minim 10 bucati )
|
|
|
Memorat
|
|
|
|
•Darth_Niculus
|
|
« Răspunde #16 : Februarie 24, 2007, 21:25:07 » |
|
Daca mai convinge inca 9 oameni .....
|
|
|
Memorat
|
|
|
|
|
•filipb
|
|
« Răspunde #18 : Februarie 24, 2007, 22:14:11 » |
|
Ideea e cu complexitatea e ca e aproximeaza numarul mediu de operatii pe care le poate efectua algoritmul tau, nu numarul exact de operatii pe care le efectueaza. Pentru complexitati exista factori constanti ( care nu au nici o legatura cu variabile din problema), de exemplu un algoritm de genul: for (i = 1; i <= 9; i++) for (j = 1; j <= 9; j++) { for (k = 1; k <= N; k++) ; } este liniar, adica O(N), cu toate ca numarul de operatii este 81N. In plus, se pastreaza cea mai mare putere din polinomul care descrie algoritmul. De exemplu: for (i = 1; i <= N; i++) scrie i;
for (i = 1; i <= N; i++) for (j = 1; j <= N; j++) scrie i+j; } are complexitatea O(N^2), nu O(N + N^2) - se pastreaza deci doar factorul dominant. Se mai poate scrie deci O(N) + O(N^2) = O(N^2) ( conceptual numarul medii de operatii pe care le va efectua programul, nu inseamna neaparat ca numarul de operatii este exact N^2 ) In legatura cu complexitatea logaritmica, cel mai cunoscut este cautarea binara. Ai intervalul [1, N] si il tot injumatatesti. Deci il poti injumatati de K ori maxim, unde 2^K <= N, si cum K = logN, complexitatea unui astfel de algoritm e O(log N). Daca repeti de N ori acest procedeu, obtii de exemplu: O(N) * O(logN) = O(N * log N). Sper ca ti-ai format macar niste idei
|
|
|
Memorat
|
|
|
|
•Adix
Strain
Karma: -9
Deconectat
Mesaje: 44
|
|
« Răspunde #19 : Februarie 25, 2007, 12:30:43 » |
|
Mersi tuturor pentru raspuns ... Mi s-a mai clarificat acuma cum sta treaba cu complexitatea, am cautat pe wiki si am gasit pana la urma aici: http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions ceva care sa explice pt fiecare tip d complexitate ce algoritm i se potriveste. (asta in cazul in care mai exista dinastia ca mine care nu inteleg O-ul ala )
|
|
|
Memorat
|
|
|
|
|
•svalentin
|
|
« Răspunde #21 : Februarie 25, 2007, 14:58:19 » |
|
[...]ceva care sa explice pt fiecare tip d complexitate ce algoritm i se potriveste Vezi sa nu te incurci cu modaliatetea asta de gandire. Nu e bine sa cauti ce algoritm are complexitatea X; mai bine invati pentru un algoritm cum sa ii calculezi complexitatea. Dar oricum, iti trebuie putine cunostiinte matematice ca sa intelegi mai bine cum sa calculezi aceste complexitati.. Articolul de pe TopCoder este destul de bun, insa o mica precizare - in tabelul respectiv cu complexitatiile si Nul maxim ce intra in timp, acel tabel este pentru calculatorul de la TopCoder, pentru un timp maxim de executie de 8 secunde. Majoritatea problemelor ce 0.1s; astfel O(N) are N maxim 1 milion, O(N 2) cam 1000 samd. Totodata conteaza mult ce fel de operatii faci si cat de multe faci. Adica un program cu 100 de foruri de O(N) s-ar putea sa mearga mai greu decat un program in O(N logN), desi dupa analiza complexitatii ar trebui sa mearga mai repede. Ce vreau sa iti zic este ca O(N) este mai rapid decat O(N logN) pentru valori infinit de mari ale lui N. Acel 100 este ceea ce o sa mai intalnesti in discutii ca fiind 'constanta'. Un alt exemplu de diferenta de 'constanta' - ai un singur for in O(N), dar care face operatii matematice complexe (radical, logaritm, arctangen..) pe cand acel O(N logN) sa faca doar niste simple adunari. Pentru valori mici ale lui N, O(N logN) va merge mai rapid. Ca sa iti fie mai usor sa intelegi toate astea iti trebuie exercitiu; incearca ca la fiecare program pe care il scrii sa incerci sa ii analizezi complexitatea. O parcurgere in latime ce complexitate are? Un program care incearca toate solutiile posibile (backtracking de exemplu) ce complexitate are? E recomandat oricum sa intelegi teoria pentru a putea pune in practica asta
|
|
|
Memorat
|
|
|
|
|