[Algorytmy] Wstawianie k nowych elementów

matematyka464 · Post autor: **matematyka464** » 8 lut 2015, o 22:51

Witam,
Wykaż, że \(\displaystyle{ k}\) nowych elementów można wstawić do ciągu uporządkowanego (\(\displaystyle{ n}\) elementów) przy pomocy \(\displaystyle{ O(k \log k + n)}\) porównań.

Prawdę powiedziawszy nie wiem jak się do tego zabrać, pokażę co ja uważam.

Posortujemy te elementy w czasie \(\displaystyle{ k \log k}\). Teraz pozostaje scalić te dwa ciągi. I to można w czasie \(\displaystyle{ n}\). Jednak nie mam pewności czy to jest dobrze, bo nie za wiele tutaj wykazałem.

bartek118 · Post autor: **bartek118** » 9 lut 2015, o 10:43

O to chodzi; uzasadniłbym jedynie czemu można je scalić w czasie \(\displaystyle{ n}\)

matematyka464 · Post autor: **matematyka464** » 9 lut 2015, o 11:02

Ok, dzięki. Nie wiedziałem, że takie coś może posłużyć za dowód. W takim razie wieczorem spróbuję przemyśleć to scalanie (nie mam 100% pewności czy się uda).

bartek118 · Post autor: **bartek118** » 9 lut 2015, o 11:09

matematyka464 pisze:Ok, dzięki. Nie wiedziałem, że takie coś może posłużyć za dowód. W takim razie wieczorem spróbuję przemyśleć to scalanie (nie mam 100% pewności czy się uda).

Algorytm scalania możesz wprost wziąć z końcowego etapu sortowania przez scalanie.

matematyka464 · Post autor: **matematyka464** » 9 lut 2015, o 11:41

Jak widać w zadaniu rozchodzi się o porównania. Żeby scalić potrzebujemy wykonać nie mniej niż \(\displaystyle{ n}\) porównań. Gdy wykonamy już te \(\displaystyle{ n}\) porównań to jeśli zostały jakieś elementy spośród \(\displaystyle{ k}\) elementów to nie musimy ich porównywać, doklejamy je "na końcu".

Ok ?

I druga część:
Wykaż, że dla \(\displaystyle{ k\ge n}\) rozwiązanie jest asymptotycznie optymalne. Nie wiem za bardzo jak to wykazać.