W dniu 2011-08-15 16:53, slawek pisze:
>
> Użytkownik "bartekltg" <b...@o...pl> napisał w wiadomości grup
> dyskusyjnych:j2b94f$4j5$...@n...onet.pl...
>> Zawsze mnie uczyli, że algorytm działa w miejscu, jeżeli
>> używa stałej ilości pamięci. O(1).
>
> Ale algorytm odwracania kolejności używa także danych wejściowych, a
> tych jest O(N). Więc nawet jak jest "in place" to jest O(N) pod względem
> użycia pamięci, sic!

> ;)

OK, jest uśmieszek, ale jakby ktoś czytał, to złożoność
pamięciową określa się jako ilość _dodatkowej_ pamięci,
poza danymi wejściowymi (i określa się w stosunku do niej).

Heapsort jest w miejscu, bo poza kilkoma zmiennymi
manewruje tylko pot tablicy, qsort nie, bo potrzeba
miejsca na stosie.

BTW, http://en.wikipedia.org/wiki/In-place_algorithm
jak przykład jest właśnie to, co podejrzewamy,
że zadał królik.


> Niekoniecznie - na x86 jest xchg - to draństwo robi prawie prawdziwy
> swap. Prawie, bo potrzebne jest xchg memory1, memory2, a tego chyba nie
> ma. Ale na x86 świat się nie kończy. Może jakby się wysilić, to
> kombinując coś z hardware, adresowaniem pamieci, DMA - być może dałoby
> się zrobić zmianę kolejności bez dodatkowych zmiennych (nawet takich
> register).

Tylko po co...

> Można też po prostu zrobić dzidzię-klasę z odpowiednim operator[], ale w
> istocie rzeczy jest to takie samo rozwiązanie, jakie wcześniej wykluczyłem.

Ale
1.wykluczyłeś je wbrew powszechnie przyjętej terminologii.
2.to co chcesz zrobić jest niewykonalne, przecież
i ramka funkcji zajmuje miejsce, i kod (w inny miejscu
pamięci) ;-)

>> (kandydat pewnie chciał przepisywać tablicę).
>
> Są trzy możliwości, od najbardziej do najmniej prawdopodobnej: kandydat
> się przestraszył (czyli niska odporność na stres) i nie zrozumiał o co
> chodzi (czyli zawiodła komunikacja człowiek-człowiek); kandydat miał
> lipny dyplom; kandydat robił sobie jaja.

Raczej 'algorytmy były na drugim roku a ja to od php jestem'.

Mam kontakt z studentami bardzo dobrej uczelni. Większość
jest rozsądna, ale zdarzają się kwiatki, od których
mi się jeży włos na głowie (a jestem 'spoza branży').


pzdr
bartekltg