Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
180 views

Στο μάθημα (αν θυμάμαι καλά) είχαμε αναφέρει ότι στην ML δεν είναι εφικτό να πάρεις κατ' ευθείαν το τελευταίο στοιχείο μιας λίστας, σε αντίθεση με το πρώτο (hd x). Εδώ βρήκα ότι υπάρχει η συνάρτηση val last : 'a list -> 'a (List.last), που δίνει πράγματι το τελευταίο στοιχείο. Δυστυχώς, ο ιστότοπος δεν αναφέρει κάτι για την πολυπλοκότητά της. Η ερώτηση μου, λοιπόν, είναι εάν έχει καλή πολυπλοκότητα η List.last, δηλαδή $Ο(1)$ κι όχι $Ο(n)$ (=κάθε φορά που την καλώ να διατρέχει όλη τη λίστα μέχρι να φτάσει στο τέλος).

in pl1 by (420 points) | 180 views
+1

Η απάντηση είναι από κάτω. Αφήνω εδώ και το πώς υλοποιεί η smlnj την last :

fun last [] = raise Empty
      | last [x] = x
      | last (_::r) = last r

1 Answer

0 votes
Best answer

Αυτό ακριβώς κάνει και έχει πολυπλοκότητα $O(n)$. Οι λίστες της ML είναι κατ' ουσίαν απλά συνδεδεμένες λίστες και δεν υπάρχει αποδοτικός τρόπος να πάρεις το τελευταίο στοιχείο τους.

by (9.5k points)
selected by

301 questions

289 answers

288 comments

769 users