Προγραμματιστική απορία πάνω σε αλγόριθμο

[defacer]

Ίσως να είναι παρόμοια ιδέα, όπως είπα έχω κρατήσει σε 2 πίνακες μονοδιάστατους τα σημεία του Χ άξονα και μετά τα σημεία του Υ άξονα. Σε μία κόπια αυτών, τους σορτάρω και ξεκινάω να βρω τα partial sums(απο αριστερα προς τα δεξια και το αναποδο) δηλαδη για το παραδειγμα S ={7, 12, 17, 26} και L= {26, 19, 14, 9}

 

Ο τρόπος είναι ουσιαστικά ο ίδιος (λογικό, δύσκολο να υπήρχαν 2 διαφορετικές O(n) λύσεις), απλά δεν είναι απαραίτητο να υπολογίσεις τα sums απο πριν. Αν δεν το κάνεις (όπως εγώ) τότε χάνεις τη δυνατότητα για random access υπολογισμό και αναγκαστικά πρέπει να γίνει σαν stream -- με τη δική μου μέθοδο η εύρεση του αποτελέσματος για ένα και μόνο τυχαία επιλεγμένο point είναι πάντα O(n) ακόμα κι αν ξέρεις από πριν ότι θα γίνει κατ' επανάληψη, ενώ με τη δική σου είναι amortized Ο(1). Tradeoffs.

[παπι]

Οριστε. Χωρις sorts και πινακες.

 

τα iteration ειναι 12 για ολα με ολα (ουσιατικα ειναι μεγεθος πινακα ^ 2 - μεγεθος πινακα). αν ειναι για ενα τοτε ειναι οσο ειναι ο πινακας.

[Anubis13]

Ενδιαφέρον παπί,

μπορείς να μου πεις πώς το έκανες?

[παπι]

Στο ειπα στο #31

Abstraction

Εβαλα αυτη την συναρτηση στο vec2

float hlLen(const vec2& other) const
	{
		return 
			std::abs(std::abs(other.x) - std::abs(x))
			+ std::abs(std::abs(other.y) - std::abs(y));
	}

Που ειναι ουσιαστικα η αποσταση οπως την θες εσυ. Και τα υπολοιπα... ειναι σα να θες να βρεις την μικροτερη αποσταση σε μονοδιαστατο χωρο.