Quote:
Originally Posted by Tolnaftate2004
PHP Code:
function S3(arrA,arrB) { temp.intersect.clear(); temp.sets.clear(); if (arrA.size() > arrB.size()) temp.c = {arrB,arrA}; else temp.c = {arrA,arrB};
for (elmt: temp.c[0]) { if (elmt in temp.c[0]) temp.intersect.add(elmt); }
temp.len = temp.intersect.size(); for (temp.i=0; temp.i<temp.len-2; temp.i++) { for (temp.j=temp.i+1; temp.j<temp.len-1; temp.j++) { for (temp.k=temp.j+1; temp.k< temp.len; temp.k++) { temp.sets.add({temp.intersect[temp.i],temp.intersect[temp.j],temp.intersect[temp.k]}); } } } return temp.sets; }
This has O(N+N!/((N-3)!*3!)), N ≤ min{a.size(),b.size()}.
|
^_^ this is an open discussion. Please explain why this is better then the naive algorithm
Also, in your big O, did you include the search time for the "in" operator in your intersect portion? I can see a few ways to optimize that.