OPTIM pro MERGESORT

[Tuetschek]

Ahoj,
cetl jste nekdo prosim popis "Slevani nestejne dlouhych posloupnosti" ve skriptech Haldy.ps od strany 28?

Definuje se tam (str. 30) jakysi algoritmus OPTIM, ktery ma zaridit vybrani toho nejlepsiho poradi slevani, aby MERGESORT probehl nejrychleji. No a ja si nejsem jisty tim, podle ceho se to vybira ... je tam

Kód: Vybrat vše

c(v):=x_{phi^-1(v)}

To znamena, ze napr. pro posloupnost prvku

Kód: Vybrat vše

34,23,83,110,3

bude

Kód: Vybrat vše

c(1):=34,c(2):=23 ...

atd?

A co znamena "V je množina jednoprvkových stromů"?

Mozna se ptam na uplne blbosti, nejak mi to posledni dobou nemysli, kdybyste nekdo vedel, co tim basnik myslel, budu vam vdecny .

[Hugo]

Mozna dotazy spatne chapu - ale co se ti nezda na 1-prvkovem stromu?:) To zobrazeni muze byt napr. jak pises, nebo nemusi, zavisi na te bijekci..

[Tuetschek]

Mozna dotazy spatne chapu - ale co se ti nezda na 1-prvkovem stromu?:) To zobrazeni muze byt napr. jak pises, nebo nemusi, zavisi na te bijekci..

Diky, ten 1-prvkovy strom uz jsem skousnul , ale to zobrazeni mi je porad divne, ma trochu moc indexu . Tu bijekci si volim libovolne?

[Hugo]

Ja tomu rozumim, ze mas napr. x1 = 3, x2 = 5, x3 = 8 (musi byt neklesajici) a bijekce je napr. x1 -> v2, x2 -> v1, x3 -> v3 (je pres indexy v posloupnosti a nevim, jak se na ni prijde).
A ted prochazi vsechny vrcholy : c(v1) = 5, c(v2) = 3, c(v3) = 8. Podiva se, co na dany vrchol ukazuje dle indexu a to tam priradi..

[Hugo]

Jeste me napadlo, jestli neni jedno, jakou tu bijekci zvolim (dulezite je, ze tam vubec nejaka je). Po prirazeni do c(v)pri vystavbe stromu uz v tom algoritmu to zobrazeni v ramci bijekce stejne nehraje roli..nebo se pletu?

[Tuetschek]

A jak potom vypada hodnota te c() pro sliti dvou vrcholu ?

[Hugo]

no, secte se, jsou to delky posloupnosti..

[Tuetschek]

no, secte se, jsou to delky posloupnosti..

Aaa ono x_1, x_2, .... jsou DELKY a ne prvky ... no konecne to chapu, omlouvam se za natvrdlost. Diky .