Diotima όχι μην μπλέκουμε τα πράγματα, κανείς μας δεν μίλησε για μοναδιαίο σύστημα αρίθμησης. Στα μοναδιαία συστήματα, ένας π.χ. 64 bit αριθμός χρειάζεται 18446744073709551616 ψηφία για την αναπαράστασή του, και άρα κανένας σύγχρονος Η/Υ δεν θα χωρούσε ούτε μία μεταβλητή, πόσο μάλλον να κάνει πράξεις με αυτήν.
Επίσης, το πρόβλημα των πρώτων (primary) αριθμών στο μοναδιαίο σύστημα αρίθμησης είναι πολυωνυμικό και όχι εκθετικό ως προς τα bits εισόδου, κι ο Γιώργος μιλούσε για εκθετική πολυπλοκότητα.
Δεν έγραψα ότι στους Η/Υ η αναπαράσταση γίνεται με το μοναδιαίο σύστημα Άλκη, αυτό που είπα είναι ότι όταν αντιλαμβανόμαστε αριθμητικά μία ακέραια ποσότητα τότε ο αριθμός π.χ 7=1+1+1+1+1+1+1 στο μοναδιαίο και θέλουμε 7 το πλήθος ψηφία για να τον αναπαραστήσουμε, στο δυαδικό 7=1*2^2+1*2^1+1*2^0 και θέλουμε 3 ψηφία και στο δεκαδικό 7= 7*10^0 ένα μόνο ψηφίο. Τον αριθμό σαν αριθμητική ποσότητα τον καταλαβαίνουμε με βάση το 1.
Πριν από όλα θα πρέπει να επιβεβαιώσουμε ότι εννοούμε το ίδιο πράγμα λέγοντας uniform και logarithmic cost models. Αυτό που καταλαβαίνω εγώ από τη Wikipedia είναι ότι μιλάμε για το πόσα βήματα μετράει σε κάθε πράξη. Έτσι αν έχω να προσθέσω 2 αριθμούς με 10 bits το uniform μετράει μια πράξη όλη την πρόσθεση, ενώ το logarithmic μετράει 10 πράξεις (που είναι ο λογαρίθμος του αριθμού που δίνεται σαν είσοδο).
Κι εγώ έτσι νόμιζα αλλά δε νομίζω πλέον ότι λέει αυτό, για αυτό παραθέτω τους ορισμούς από το wikipedia:
the uniform cost model, also called uniform-cost measurement (and similar variations),
assigns a constant cost to every machine operation, regardless of the size of the numbers involved
the logarithmic cost model, also called logarithmic-cost measurement (and variations thereof),
assigns a cost to every machine operation
proportional to the number of bits involved
Τόνισα με bold εκεί που νομίζω ότι γίνεται το λάθος κατανόησης. Το "a cost" δε σημαίνει "constant cost", όπως στην πρώτη περίπτωση. Αυτό που καταλαβαίνω είναι ότι το λογαριθμικό μοντέλο εκχωρεί ένα (κάποιο) κόστος σε κάθε λειτουργία μηχανής ανάλογα με τον αριθμό των bits που εμπλέκονται. Το ανάλογα μάλλον δεν το θεωρεί με τη μαθηματική αναλογία, διαφορετικά θα έλεγε "σταθερό κόστος", αλλά με την έννοια του "σε σχέση" με τον αριθμό των bits που εμπλέκονται.
Δηλαδή, όσον αφορά την πολυπλοκότητα, όταν θεωρώ το κόστος με βάση τα bits εισόδου συσχετίζω το κόστος της μηχανής με το πλήθος των bits εισόδου, άρα χρησιμοποιώ λογαριθμικό μοντέλο. Π.χ. στον αλγόριθμο που πρότεινες Γιώργο και έγραψα εγώ τη συνάρτηση f(m)=2^m όπου m=logn, αν ζωγραφίσω τη γραφική παράσταση στον οριζόντιο άξονα θα αυξάνω κατά 1 τα bits και η συνάρτηση θα μου δίνει στον κάθετο άξονα το πλήθος των πράξεων σε σχέση με το πλήθος των bits εισόδου.
Το uniform cost model μάλλον μου "απαγορεύει" να εκφράσω έτσι τη συνάρτηση, άσχετα αν το input γίνεται σε bits. Με τα μαθηματικά φυσικά μπορώ και το κάνω.
Δεν ξέρω αν τα κατάλαβα καλά, αυτό νομίζω θέλει να πει ο Άλκης, περιμένω απάντηση.
