referring wikipedia's article: https://en.wikipedia.org/wiki/sorting_network , focus on paragraph constructing sorting networks.
can please explain size, upper bound , size, lower bound (in table) are? expect lower bound refers minimum connections needed correctly sort input of n numbers (am correct?). if so, why bother upper bound? in theory, 1 use number of connections larger upper bound how can established? have read linked paper (ref. 11) still confused.
the paragraphs after table give hint meaning of upper bound , lower bound:
for 1 ten inputs, minimal (i.e. size-optimal) sorting networks known, , higher values, lower bounds on sizes s(n) can derived inductively using lemma due van voorhis: s(n + 1) ≥ s(n) + ⌈log2(n)⌉.
the « upper bound » in table apparently corresponds size of size-optimal sorting network currently known given number of elements sort. known size-optimal sorting networks 1 10 elements have been proven optimal, we're not sure known size-optimal sorting networks more elements optimal ones. « lower bound » corresponds theorical minimal size of sorting network sort given number of elements: may possible sorting network of size not exists, haven't proven yet.
to sum up:
- « upper bound » represents size-optimal sorting network has been found.
- « lower bound » represents theorical minimal size of network. has not been proven such network not exist, haven't found viable network of size either.
as side note maintain a library size-optimal sorting networks, , sizes correspond « upper bound » table (see the documentation , the implementation).
Comments
Post a Comment