Δημοσιεύτηκε: 21 Οκτ 2011, 20:07
Λεπόν σταρλαιτ. Έγραψα για 1 φεγγάρι και εξαφανίστηκα. Για την πολυπλοκότητα βρίσκεις το πλέον χρονοβόρο σημείο και προσπαθείς να υπολογίσεις τις πράξεις που θα γίνουν συναρτήσει της εισόδου.
Έτσι στη bubblesort είναι προφανές ότι όλες οι πράξεις γίνονται μέσα στο for. Συνολικά βλέπεις ότι γίνονται (Ν-1)+(Ν-2)+...+2+1 πράξεις. Απ το γνωστό τύπο των αριθμητικών προόδων προκύπτει ότι αυτό κάνει N(Ν-1)/2. Αν κάνεις τις πράξεις θα βγει ½(Ν²-Ν). Το ½ είναι σταθερά, οπότε ασυμπτωτικά δε μας αφορά. Το Ν είναι αμελητέο μπροστά στο Ν² για μεγάλες τιμές και έτσι συνολικά η πολυπλοκότητα είναι Ο(Ν²).
Έτσι στη bubblesort είναι προφανές ότι όλες οι πράξεις γίνονται μέσα στο for. Συνολικά βλέπεις ότι γίνονται (Ν-1)+(Ν-2)+...+2+1 πράξεις. Απ το γνωστό τύπο των αριθμητικών προόδων προκύπτει ότι αυτό κάνει N(Ν-1)/2. Αν κάνεις τις πράξεις θα βγει ½(Ν²-Ν). Το ½ είναι σταθερά, οπότε ασυμπτωτικά δε μας αφορά. Το Ν είναι αμελητέο μπροστά στο Ν² για μεγάλες τιμές και έτσι συνολικά η πολυπλοκότητα είναι Ο(Ν²).