Hi there bsxiong,
Quote:
|
What is the fewest possible number of item comparisons done by the algorithm?
|
One, if the first two items provided the match.
If the last two items provided the match then the the total number of comparisons/iterations would be...
n!/((n-2)! x 2) in the example below this would equate to 45
...of course, this value is also the total number of iterations for no matches.
Code:
<script type="text/javascript">
var a=[1,2,3,4,5,6,7,8,9,0];
var n=a.length;
var b=0;
var c,i,j;
window.onload=function() {
for(i=0;i<n-1;i++) {
for(j=i+1;j<n;j++) {
b++;
if(b==1){
c='iteration';
}
else{
c='iterations';
}
if(a[i]==a[j]){
alert('duplicate found after '+b+' '+c);
return;
}
}
}
alert('no duplicate found after '+b+' '+c);
}
</script>
Add to del.icio.us 
Can you digg it?
Linear Mode
