Re: var�andi lesefni til pr�fs. -- SkilaboÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ°askjÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ³ÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ°a TÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ¶lvunarfrÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ¦ÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ°i 2

[ Show ]

Support VoyForums

[ Shrink ]

VoyForums Announcement: Programming and providing support for this service has been a labor of love since 1997. We are one of the few services online who values our users' privacy, and have never sold your information. We have even fought hard to defend your privacy in legal cases; however, we've done it with almost no financial support -- paying out of pocket to continue providing the service. Due to the issues imposed on us by advertisers, we also stopped hosting most ads on the forums many years ago. We hope you appreciate our efforts.

Show your support by donating any amount. (Note: We are still technically a for-profit company, so your contribution is not tax-deductible.) PayPal Acct: Feedback:

Donate to VoyForums (PayPal):

[ Login ] [ Contact Forum Admin ] [ Main index ] [ Post a new message ] [ Search | Check update time ]

[ Next Thread | Previous Thread | Next Message | Previous Message ]

Date Posted: 11:48:10 04/29/02 Mon
Author: Hj�lmt�r
Subject: Re: var�andi lesefni til pr�fs.
In reply to: 's message, "var�andi lesefni til pr�fs." on 10:36:39 04/29/02 Mon

>Hvar er a� finna efni� um val � k minnstu st�kum me�
>�tsl�ttarkeppni og ne�ri m�rk � r��un, samkv�mt
>leslista til pr�fs.?

�a� var n� bara � fyrirlestri. �etta er ekki � b�kinni.

�tsl�ttarkeppnin var um a� l�ta st�kin keppa me� �tsl�tti, �ar sem minna staki� vinnur � hverjum leik, �ar til a�eins
eitt stak er eftir. �� er �a� minnsta staki�. Til a� finna n�stminnsta staki� �� arf ekki a� sko�a �ll hin
st�kin, �v� n�stminnsta staki� hl�tur a� hafa tapa� fyrir �v� minnsta. Ef st�kin eru N �� eru a�eins log(N) st�k
sem t�pu�u fyrir minnsta stakinu (�.e. � �rslitunum, � undan�rslitunum, �tta-li�a �rslitum, o.s.frv.)

Vi� �urfum �v� a�eins log(N)-1 samanbur� til a� finna n�stminnsta staki� (eftir a� hafa nota� N-1 samanbur�i til
a� finna minnsta staki�). S��an m� halda �fram og finna �ri�ja minnsta staki�. �a� hl�tur a� hafa tapa� fyrir �v�
minnsta e�a n�stminnsta, svo �� koma � mesta lagi um 2*log(N) st�k til greina.

�g f�r ekki mj�g �tarlega � �essa greiningu � fyrirlestrinum, heldur var �g a�allega a� s�na a� �a� er
stundum h�gt a� n�ta s�r �� vinnu sem b�i� er a� vinna (�.e. a� finna minnsta staki�) til a� fl�ta fyrir ��rum
�treikningi (�.e. finna n�staminnsta).

Ne�ri m�rk � r��un eru ekki � b�kinni, en eru � n�stum �llum ��rum b�kum um reiknirit! Flj�tlegast er l�klega
a� leita � Vefnum, t.d. a� "lower bounds for sorting". �� kemur miki� efni um �etta.

�g f�r heldur ekki mj�g dj�pt � �etta � fyrirlestrinum, heldur var a�allega a� s�na a� �a� ERU ne�ri m�rk � �v�
hver hratt er h�gt a� ra�a.

[ Next Thread | Previous Thread | Next Message | Previous Message ]