Αναδρομική σχέση

[Mathletic]

Γειά! 

 

Πώς μπορώ να βρώ μία αναδρομική σχέση που περιγράφει το κόστος του αλγορίθμου ταξινόμησης Quicksort όταν θέλουμε να διαμερίσουμε τα υποπροβλήματα με λόγο 9:1 ?

 

Ο αλγόριθμος είναι ο εξής:

Quicksort(A,p,r)
   if p<r then
      q<- partition(A,p,r)
      Quicksort(A,p,q-1)
      Quicksort(A,q+1,r)

 

 

[mtsouk]

Επειδή διάβαζα σχετικά με τον Quicksort τελευταία, δεν νομίζω να βρεις αυτό που ψάχνεις ("αναδρομική σχέση") έτσι όπως το ψάχνεις.

Ο Quicksort έχει n*logn και στην χειρότερη περίπτωση n*n.

Δες καλύτερα ένα βιβλίο με αλγόριθμους - όλα σχεδόν αναφέρουν τον quicksort και αναλύουν το κόστος του.

 

φιλικά,

[albNik]

Αυτο που ζηταει ειναι το κοστος αν σε καθε βήμα το σπάσουμε σε 9 υποπροβληματα αντι για 2. σε 2 υποπροβληματα με λογο 9 : 1 αντι για 2 ισα.

Για 2 ισα εχουμε:

T(n) = 2T(n/2) + O(n) = O(nlog(n))

 

 

http://en.wikipedia.org/wiki/Master_theorem

[defacer]

Η ερώτηση για το ένα εκατομμύριο ευρώ είναι: εφόσον μιλάμε για quicksort, το μέγεθος των υποπροβλημάτων εξαρτάται από την επιλογή του pivot. Δεδομένου ότι η επιλογή του pivot "πρέπει" να είναι Ο(1) γιατί αλλιώς δεν έχεις πια quicksort, πώς ακριβώς θα βρεις σε O(1) pivot τέτοιο που να τα χωρίζει συγκεκριμένα με λόγο 9:1; Ποιός σου εγγυάται καν ότι θα υπάρχει τέτοιο pivot;

[albNik]

Μα η ερωτηση ειναι υποθετική.

Ας πουμε εσυ επιλεγεις για pivot παντα το πρωτο στοιχείο (σε O(1)) και οι αριθμοι ηταν τοποθετημενοι ετσι ωστε επιλέγοντας το πρωτο να εχεις 10% στοιχεια απο τα αριστερα και 90% απο τα δεξια.

Η αναλυση για το υποθετικο 50%-50% (best case nlogn) και 0-100 (worst case n*n) ειναι γνωστή.

Εδω ζητάει το 90%-10%.

[defacer]

Θα συμφωνούσα μαζί σου αν δεν έλεγε

 

Πώς μπορώ να βρώ μία αναδρομική σχέση που περιγράφει το κόστος του αλγορίθμου ταξινόμησης Quicksort όταν θέλουμε να διαμερίσουμε τα υποπροβλήματα με λόγο 9:1 ?

 

Έτσι που είναι δεν είμαι σίγουρος τι εννοεί.