Πολύ ενδιαφέρον το quiz για το Fibonacci, με όντως άσχημη υλοποίηση σε java
Βέβαια για να είμαστε ακριβείς, το static HashMap που χρησιμοποιούμε μπορεί να μας επιτρέψει να απαντήσουμε ερωτήματα σε O(1) (εφόσον έχουν υπολογιστεί σε προηγούμενες κλήσεις), αλλά το πληρώνουμε αυτό με υπερμεγέθες κόστος σε χωρική πολυπλοκότητα (Ο(MaxNum) θεωρητικά, πρακτικά από ένα σημείο και μετά OutOfMemoryException
)
Ακόμα και αν το HashMap δεν ήταν static state, και το είχαμε ενσωματώσει στο σώμα της μεθόδου (μετατρέποντας τη μέθοδο από αναδρομική σε επαναληπτική, ή εναλλακτικά περνώντας αλυσιδωτά το HashMap ώς παράμετρο στη μέθοδο), παρατηρείστε πως λόγω της αποθήκευσης όλων των ενδιαμέσων τιμών, η πολυπλοκότητα χώρου του αλγορίθμου γίνεται O(n). Μπορούμε να το βελτιώσουμε αυτό, παρατηρώντας πως σε κάθε βήμα του Fibonacci, χρειαζόμαστε μόνο τις 2 προηγούμενες τιμές. Έτσι, μπορούμε να ρίξουμε την πολυπλοκότητα χώρου σε O(1) υπολογίζοντας ως εξής:
Code: Select all
public static long linearFibonacci(long n)
{
long memory[] = {0, 1};
if (n < 2)
return memory[0];
else if (n == 2)
return memory[1];
long fib = 0;
for (long i = 3; i <= n; i++)
{
fib = memory[1] + memory[0];
memory[0] = memory[1];
memory[1] = fib;
}
return fib;
}
H οποία έχει πολυπλοκότητα χρόνου O(n) που είναι και το ζητούμενο εξαρχής, όντας όμως μακράν οικονομικότερη σε χώρο (μνήμη).