Προτάσεις σχετικές με αλγορίθμους

[Mathletic]

Γειά

Θέλω να ελέγξω εάν οι παρακάτω προτάσεις είναι σωστές ή όχι και να δώσω μία σύντομη εξήγηση για την επιλογή μου.
1. Πολυωνυμικός: καλός . Εκθετικός: κακός.
2. Ο αλγόριθμος Radix sort δουλεύει σωστά όταν χρησιμοποιείς οποιονδήποτε σωστό αλγόριθμο ταξινόμησης για να ταξινομήσεις κάθε ψηφίο.
3. Δοθέντος ενός πίνακα από ακεραίους, ο χρόνος που παίρνει ο Counting Sort είναι πολυωνυμικός σε σχέση με το μέγεθος εισόδου .
4. Δοθέντος ενός πίνακα από ακεραίους, ο χρόνος που παίρνει ο HeapSort είναι πολυωνυμικός σε σχέση με το μέγεθος εισόδου .
5.Για έναν αλγόριθμο Δυναμικού Προγραμματισμού, ο υπολογισμός όλων των τιμών με bottom-up είναι ασυμπτωτικά ταχύτερος από την χρησιμοποίηση αναδρομής και
memoization.
6. Ο χρόνος ενός δυναμικού αλγορίθμου είναι πάντα Ο() όπου είναι ο αριθμός των υποπροβλημάτων.
7. Κάθε πρόβλημα που ανήκει στο ΝΡ επιλύεται σε εκθετικό χρόνο.

Προσπάθησα τα εξής:

1. Σωστό. Πώς μπορεί όμως να δικαιολογηθεί;
2. Λάθος. Ο αλγόριθμος ταξινόμησης πρέπει να είναι ευσταθής. Πώς μπορεί να αιτιολογηθεί περαιτέρω;
3. Σωστό. Ο χρόνος που παίρνει ο Counting Sort είναι γραμμικός σε σχέση με το μέγεθος εισόδου , άρα είναι πολυωνυμικός.
4. Σωστό. Ο χρόνος που παίρνει ο HeapSort είναι και αφού ο χρόνος είναι πολυωνυμικός.
5. Λάθος. Ισχύει το αντίθετο.
6-7. Μπορείτε να μου δώσετε μία ιδέα για το τι πρέπει να σκεφτούμε για να να αποφασίσουμε αν είναι σωστές οι προτάσεις αυτές ή λανθασμένες;