-
Data: 2009-03-02 23:23:34
Temat: Re: Ile elementów mniejszych od ...
Od: "bartekLTG" <b...@o...ciach.pl> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]Mirek wrote:
> Witam,
>
> od pewnego czasu nurtuje mnie tytułowe pytanie: "Ile elementów
> w zadanym zbiorze jest mniejszych od wybranego elementu?"
>
> Dla dość specyficznej relacji częsciowego porządku szukam
> efektywnej struktury/algorytmu, która ułatwi mi odpowiedź na to
> pytanie.
>
> O to charakterystyka zbioru:
>
> - Zbiór unikalnych elementów E={e[i],i=1...N} o liczności rzędu 10^6
>
> - Każdy element posiada pewną liczbę cech (obiekty mają rożne
> ilości cech), oznaczmy to e[i]={e[i,j],j=1...n_i}, średnia
> liczność cech w zbior E wynosi około 30-50, tzn.:
> sum_i #e[i] ~= 50*#E
>
> - Każda cecha e[i,j] jest uporządkowawaną parą liczb dodatnich:
> e[i,j] = ( e[i,j,1], e[i,j,2] ), gdzie e[i,j,1] <= e[i,j,2].
> (równość zachodzi co najwyżej dla jednej cechy w elemencie)
>
> - Relacja częściowego porządku cech:
>
> e[i1,j1] < e[i2,j2] <==>
> (e[i1,j1,1] < e[i2,j2,1]) & (e[i1,j1,2] < e[i2,j2,2])
>
> Każda cecha (czyli para liczbowa) jest unikalna w całym
> zbiorze E, więc relacja e[i1,j1] = e[i2,j2] zachodzi tylko
> gdy i1=i2 i j1=j2. Nie wszystkie cechy są porównywalne wg
> powyższej definicji. W dodatku *żadne* dwie cechy danego
> elementu nie są porównywalne.
>
> - Na koniec właściwa relacja porządkująca elementy e[i]:
>
> e[i1] < e[i2] <==>
> istnieje choć jedna para j1,j2: e[i1,j1] < e[i2,j2]
>
> Definicja jest jednoznaczna/niesprzeczna, tzn. jeżeli
> dla danych i1,i2 istnieją powyższe j1,j2, to nie istnieją
> k1, k2 takie, że zachodzi relacja odwrotna e[i1,k1] > e[i2,k2].
Napewno?
e[1,1,1] = 50
e[1,1,2] = 51
e[1,2,1] = 2
e[1,2,2] = 3
e[2,1,1] = 48
e[2,1,2] = 49
e[2,2,1] = 4
e[2,2,2] = 5
z tego
e[1,1]>e[2,2]
e[1,2]<e[2,1]
wiec e1>e2 e2>e2 ;]
pozdr
--
bartekltg
...aby UseNet rósł w siłę a trolle żyły dostatnio.
Następne wpisy z tego wątku
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-28 Co dalej z Izerą...
- 2024-05-28 Nowe samochody są RAKOTWÓRCZE tylko nikt tego nie chce głośno powiedzieć
- 2024-05-28 czy zabioro mu auto?
- 2024-05-27 Chińczyki mają dość czekania na tuska i te jego UROJONE audyty
- 2024-05-27 coraz trudniejsze rozmowy o OC
- 2024-05-28 Przednia lampka rowerowa Basta / AXA pod dynamo w piaście
- 2024-05-28 Boję siię capa...
- 2024-05-24 Efekt gitarowy koda kd-30 trash metal
- 2024-05-27 Re: Efekt gitarowy koda kd-30 trash metal
- 2024-05-27 Wykrywanie przerwy w długim przewodzie zakopanym w ziemi.
- 2024-05-27 PT500
- 2024-05-28 Łódź => SAP CO Consultant <=
- 2024-05-28 Białystok => Senior Developer React Native <=
- 2024-05-28 Kraków => Mid/Senior QA Engineer <=
- 2024-05-28 Wrocław => Key Account Manager <=