19. januar 2004 - 11:05Der er
8 kommentarer og 1 løsning
Hjælp til Køretidskompleksitet
Hej sidder lige og roder med en algoritme der hedder Nearest neighbour heuristic og den har følgende køretidskompleksitet, der er bare nogle af reduceringerne jeg ikke helt forstår, kan i hjælpe mig ??
Algoritmen tilføjer ét nyt punkt for hver iteration. Dermed vil antallet af iterationer være n – 1. For hver iteration skal der udføres en række sammenligninger. I 1. iteration foretages n – 1 sammenligninger. I 2. iteration foretages n – 2 sammenligninger, da vi kun undersøger kanter til punkter vi endnu ikke har besøgt. Sådan fortsættes til alle pinkterer besøgt. Alle sammenligninger kører efter formen: (n – 1) + (n – 2) + …….(n – (n – 1)).
Dette kan også omskrives til: n(n - 1)/2. <-----Hvordan ??
Heraf kan vi udlede at der foretages: (n – 1) + n(n – 1)/2 = n2/2 – n/2 – 1 <-----Hvordan ?? operationer, hvilket giver en køretidskompleksitet på O(n2)
I dette særtema ser vi på, hvordan cloud og AI bliver fundamentet for virksomhedernes digitale forretning, og hvordan de nye muligheder for automatisering og forretningsværdi kan udnyttes uden at miste overblik, sikkerhed og menneskelig kontrol.
1+2+3+...+n=(1+n)*n/2 det er summen af en differensrække med første led 1, sidste led n, differensen 1 og antallet af led n. Jeg viser om et øjeblik, hvordan man indser det.
Der knytter sig en historie til dette. Den berømte matematiker Carl Fridrich Gauss blev som barn bedt om at finde summen af tallen fra 1 til 100. Læreren troede at nu havde klassen nok at gøre, men Gauss gjorde således: 1+2+3+..+99+100= (1+100)+(2+99)+(3+99)+...+(49+52)+(50+51) her står der 50 led, som hver har summen 101. Summen bliver derfor 101*50=(1+100)*100/2
Din situation: Vi bruger formlen: sum af første og sidste led gange antallet af led delt med 2. (n-1)+(n-1)+...+(n-(n-1))=1+2+3+...+(n-1)=(1+(n-1))*(n-1)/2=n*(n-1)/2
Nu viser jeg at 1+2+...+n er (1+n)*n/2.
n lige: vi gør lige som Gauss: 1+2+...+n=(1+n)+(2+n-2)+(3+n-2)+...+(n/2+n/2+1) Der er nu n/2 led, som hver har summen 1+n. Derfor er summen (1+n)*n/2. n ulige: 1+2+...+n=1+2+...+(n-1)+n n-1 er lige, og derfor er summen af de første (n-1)-led (1+(n-1)*(n-1)/2=n*(n-1)/2
Desværre kan jeg ikke finde noget på nettet om dette. Hvor er det du har problemer i det jeg har skrevet? Bare spørg løs. Jeg vil dog lede lidt mere.
Vi kan lige her se på et konkret eksempel med n ulige:
1+2+3+...+101=(1+2+3+...+100)+101 Den første sum klares som Gauss gjorde det. Vi får derfor (1+100)*100/2+101=101*100/2+101= 101*(100/2+1)=101*102/2=101*(1+101)/2
Igen ser vi, at det bliver antallet af led gange sum af første og sidste led gange en halv.
Ups: Rettelse til mit indlæg Kommentar: nmh 19/01-2004 11:59:24
n lige: vi gør lige som Gauss: 1+2+...+n=(1+n)+(2+n-1)+(3+n-2)+...+(n/2+n/2+1) Der er nu n/2 led, som hver har summen 1+n. Derfor er summen (1+n)*n/2.
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
