Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The complexity of identifying large equivalence classes

Skyum S., Frandsen G.S., Miltersen P.B., Binderup P.G.

Fundamenta Informaticae

1999

Vol. 38, Nr 1,2

25-37

We prove that at least ...equivalence testes and no more than ... equivalence testes are needed in the worst case to identify the equivalence classes with at least k members in set of n elements. The upper bound is an improvement by a factor 2 compared to known results. For k=3 we give tighter bounds. Finally, for k>n/2 we prove that it is necessary and it suffices to make 2n-k-1 equivalence testes which generalizes a known result.