Quote:
Originally Posted by Kristi
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.
|
A good point:
O(N1*N2 + N!/((N-3)!*3!))
I had originally intended to do something along these lines:
PHP Code:
for (elmt: temp.c[0]) {
if (elmt in temp.c[1])
temp.intersect.add(elmt);
}
becomes
PHP Code:
while (temp.c[0].size()) {
temp.elmt = temp.c[0][0];
if (temp.elmt in temp.c[1]) {
temp.intersect.add(temp.elmt);
temp.c[0].remove(elmt);
temp.c[1].remove(elmt);
} else temp.c[0].delete(0);
}
Still
O(N1*N2), but often less.
It just slipped my mind. Silly me.
Also, first thing should be if (arrA.size() > 2 && arrB.size() > 2)...
As for the naive algorithm, It has
O(N2^3*N1!/((N1-3)!*3!)) (?), I think.