Re: verkefni 4 vikubla� 10 -- 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: 14:21:44 03/21/02 Thu
Author: Hj�lmt�r
Subject: Re: verkefni 4 vikubla� 10
In reply to: 's message, "Re: verkefni 4 vikubla� 10" on 12:49:01 03/21/02 Thu

>>>Mig langar til a� f� �a� � hreint hvernig O() er
>>>fundi�. F�r � soldi� rugl � d�mat�manum
>>
>>Formlega skilgreiningin er � Kafla 2 � Algorithms
>>b�kinni, en �ar eru l�ka �msar reglur sem h�gt er a�
>>nota s�r til
>>a� einfalda s�r �treikninginn og �a� er �a� sem �g hef
>>veri� a� gera � fyrirlestrum. T.d. fastar � hverjum
>>��tti
>>skipta ekki m�li ( 3N er O(N), 0.001N er O(N) ).
>>�egar tv� f�ll (��ttir) eru l�g� saman �� gildir �a�
>>fall sem vex
>>hra�ast, t.d. 3N + 0.2N^2 er O(N^2), e�a vi� getum
>>l�ka skrifa� O(N) + O(N^2) = O(N^2). �etta gildir ��
>>a�eins
>>um samlagningu, ekki margf�ldun e�a veldishafningu.
>>
>>Annars �tla �g ekki a� gefa fullkomna skilgreiningu �
>>O()-hugtakinu. �a� er langskynsamlegast a� lesa um
>>�a� � b�kinni.
>
>�g var n� eiginlega bara a� meina hvernig �a� v�ri
>fundi� �t � �essu tiltekna verkefni �a� er d�mi 4 �
>vikubla�i 10

J�, sorr�.

M�li� er a� �essi h�kkunarruna (1, 2, 4, 8, 16, ...) blandar aldrei saman oddat�lus�tum og jafnt�lus�tum �
�llum fyrri umfer�um Shellr��unar. Alltaf er veri� a� vinna me� a[i] og a[i-h], og �ar sem h er j�fn tala, ��
eru b��i i og i-h anna� hvort j�fn tala e�a b��i oddatala. �etta gerist �ar til h er sett sem 1, en �� er veri� a�
framkv�ma hreina Innsetningarr��un. � �eirri stundu er vektorinn � �essari r��:

1, N+1, 2, N+2, 3, N+3, 4, ... , N/2, N+N/2

�a� er auglj�st a� talan 2 �arf a� f�rast ni�ur um 1 s�ti til a� komast � sitt r�tta s�ti. S��an �arf talan 3 a�
f�rast um 2 s�ti (framhj� N+2 og N+1) til a� komast � sitt r�tta s�ti. S�mulei�is �arf 4 a� f�rast um 3 s�ti ni�ur.
Svona gengur �etta �ar til N/2 �arf a� f�rast ni�ur um N/2-1 s�ti til a� komast � r�ttan sta�.

Heildarfj�ldi f�rslna � �essari s��ustu umfer� Shellr��unar er ��: 1 + 2 + 3 + ... + N/2-1 = (N/2)(N/2-1)/2, sem
er u.�.b. (N^2)/8 og �a� er O(N^2).

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