Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.
Διάβασε ν
Για ι από 1 μέχρι ν
Γράψε ι
Τέλος_επανάληψης