axeto men - boitheia de

[Panagopoylos Giorgos]

Paleos Aleksandros wrote:

>Kalispera to thema mou einai entelos !asxeto! me ti lista , apla theoro oti 
>eiste oi monoi pou mporoun na me boithisoun me to problima moy......Gnosi na 
>prosferoume......Min me vrisete plz!!!
>Psaxno na bro tin polyplokotita kai tin apodeiksi tou bubblesort kaii toy 
>insertion sort (pos metafrazetai o teleytaios sta ellinika?)
>Exete kammia apantisi?
>  
>
H polyplokothta toy bubble sort einai O(n^2).
Ap:
-----
H xeiroterh periptwsh einai otan ta stoixeia einai diatetagmena kata 
fthinoysa diataksh. Ara xreiazomaste
( n - 1 ) + ( n - 2 ) + ... + 2 + 1 = ( n - 1 )n / 2 = O( n^2 ) 
sygriseis kai metatheseis stoixeiwn. Me ton idio
tropo mporeis na apodeikseis kai gia thn mesh periptwsh. Bebaia mia pio 
aplh lysh einai apo episkophsh toy
kwdika. Apoteleitai apo dyo for loops kai mia if ara polyplokothta O( n^2 ).

Oson afora thn polyplokothta toy insertion sort einai epishs O( n^2 ). [ 
Ellhnikh onomasia ...??? pantos exw
akoysei na legetai kai "Diataksh Eisagwghs" ]

Ap:
-----
H xeiroterh periptwsh einai otan ta stoixeia einai diatetagmena kata 
fthinoysa diataksh. Ara xreiazomaste
1 + 2 + 3 + ...( n - 1 ) = ( n - 1 )n / 2 = O( n^2 ) sygriseis kai 
metatheseis stoixeiwn. Me ton idio
tropo mporeis na apodeikseis kai gia thn mesh periptwsh.
1/2 + 2/2 + 3/2 + ...( n - 1 )/2 = ( n - 1 )n / 4 = O( n^2 )

>Episi kati pio dyskolo pos mporo na apodeikso oti to 2-sat den anikei sto NP?
>  
>
H apanthsh toy Giorgoy htan pisteyw katatopistikh.

>Eyxaristo poly
>Aleksandros
>
>
>
>-------------------------------------------------
>Το mail εστάλει μέσω του Τ.Ε.Ι. Αθήνας
>This mail was sent through T.E.I. of Athens
>
>  
>
Elpizw na se bohthisa...
gepanago