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

Είναι κάποιο κατηγόρημα της Prolog εκ των nth0 ή nth0_det χρονικής πολυπλοκότητας O(1); Δε διευκρινίζεται αυτό κάπου στα man pages. Αν δεν είναι, υπάρχει κάτι αντίστοιχο για την προσπέλαση συγκεκριμένου στοιχείου σε μία λίστα με μικρή πολυπλοκότητα;

in pl1 by (180 points)
edited by | 134 views

1 Answer

0 votes
Best answer

Όχι, κανένα από αυτά δεν είναι πολυπλοκότητας Ο(1). Κανένα κατηγόρημα δεν μπορεί να προσπελάζει το N-οστό στοιχείο μίας λίστας σε χρόνο Ο(1) --- ακριβέστερα, λιγότερο από Ο(Ν) --- λόγω του τρόπου με τον οποίο υλοποιούνται οι λίστες, όχι μόνο στην Prolog αλλά σε όλες τις γλώσσες. (Οι "λίστες" της Python είναι εξαίρεση, η υλοποίησή τους είναι σαν τα vectors της C++).

Αυτό που είναι Ο(1) στην Prolog και θα μπορούσες να το χρησιμοποιήσεις αν το πλήθος των στοιχείων σου είναι σταθερό, είναι το κατηγόρημα arg/3. Με αυτό μπορείς να υλοποιήσεις κάτι σαν τις tuples σε άλλες γλώσσες.

by (9.4k points)
selected by

262 questions

254 answers

274 comments

2.9k users