alphacyberranger@sh.itjust.works to Programmer Humor@programming.devEnglish · 1 year agoNot everything can be done in constant time, that's O(k)sh.itjust.worksimagemessage-square27linkfedilinkarrow-up1147
arrow-up1147imageNot everything can be done in constant time, that's O(k)sh.itjust.worksalphacyberranger@sh.itjust.works to Programmer Humor@programming.devEnglish · 1 year agomessage-square27linkfedilink
minus-squaremagic_lobster_party@kbin.runlinkfedilinkarrow-up15·1 year agoYou have two lists of size n. You want to find the permutations of these two lists that minimizes a certain distance function between them.
minus-squarecatastrophicblues@lemmy.calinkfedilinkarrow-up2·1 year agoSurely you could implement this via a sorting algorithm? If you can prove the distance function is a metric and both lists contains elements from the same space under that metric, isn’t the answer to sort both?
minus-squarejjagaimo@lemmy.calinkfedilinkarrow-up7·1 year agoIt’s essentially the traveling salesman problem
You have two lists of size n. You want to find the permutations of these two lists that minimizes a certain distance function between them.
Surely you could implement this via a sorting algorithm? If you can prove the distance function is a metric and both lists contains elements from the same space under that metric, isn’t the answer to sort both?
It’s essentially the traveling salesman problem