Algowikiadmin: Recovering wiki

2014-09-11T18:23:44Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:07Z

Recovering wiki

New page

1) Sort the sets (which takes <math>O(n \log{}n)</math>) and use the algorithm described in 2) which takes <math>O(n)</math> (which is also <math>O(n \log{}n)</math>).

2) A and B are sorted (assume in ascending order). The fact that the sets are sorted implies that there is a comparison defined on the elements of A and B (i.e. we can tell whether an element is greater, equal to or smaller than another element).

* let U be the set which will contain the union
* while A and B are not empty:
** if the first element of A is equal to the last element added to U, remove the first element of A and continue with the next iteration
** if the first element of B is equal to the last element added to U, remove the first element of B and continue with the next iteration
** if the first (lowest) element of A is strictly smaller than the first (lowest) element of B, remove the first element of A and add it to U, then continue with the next iteration
** if the first (lowest) element of A is strictly greater than the first (lowest) element of B, remove the first element of B and add it to U, then continue with the next iteration
** if the first (lowest) element of A is equal to the first (lowest) element of B, remove the first element from each A and B and add one of them to U, then continue with the next iteration

* After the while loop, either A or B or both are empty. If one of them is non-empty, add its elements to U.

← Older revision		Revision as of 18:23, 11 September 2014
Line 1:		Line 1:
−	1) Sort the sets (which takes ~~<~~math~~>~~O(n \log{}n)~~<~~/math~~>~~) and use the algorithm described in 2) which takes ~~<~~math~~>~~O(n)~~<~~/math~~>~~ (which is also ~~<~~math~~>~~O(n \log{}n)~~<~~/math~~>~~).	+	1) Sort the sets (which takes <math>O(n \log{}n)</math>) and use the algorithm described in 2) which takes <math>O(n)</math> (which is also <math>O(n \log{}n)</math>).

	2) A and B are sorted (assume in ascending order). The fact that the sets are sorted implies that there is a comparison defined on the elements of A and B (i.e. we can tell whether an element is greater, equal to or smaller than another element).		2) A and B are sorted (assume in ascending order). The fact that the sets are sorted implies that there is a comparison defined on the elements of A and B (i.e. we can tell whether an element is greater, equal to or smaller than another element).

TADM2E 4.9 - Revision history

Algowikiadmin: Recovering wiki

Algowikiadmin: Recovering wiki