Marx är nöjd med hjälpen
Marx 284
Postad: 27 feb 2020 17:33

Pascal-komplexitet

En algoritm listar samtliga (oordnade) par bland n element. Bestäm algorimens komplexitet om varje par tar ett bearbetningssteg att ta fram.


Varför blir svaret O(n2)

Laguna 14295
Postad: 27 feb 2020 20:15

Hur många par blir det? 

Marx 284
Postad: 27 feb 2020 20:56 Redigerad: 27 feb 2020 20:56
Laguna skrev:

Hur många par blir det? 

Blir antalet bearbetningssteg  n(n+1)2?

SeriousCephalopod 2157
Postad: 27 feb 2020 21:00

Frågan är egentligen lite wonky eftersom en algoritm som gör detta kan vara sämre än O(n^2). En algoritm kan trots allt inte definieras av vad den producerar (listan) utan endast hur den gör detta.

Men om man tar det på allvar att det tar "ett bearbetningsteg att ta fram" ett element så blir komplexiteten samma som antalet sådana oordnade par dvs

O(n(n+1)/2)=O(n2/2+n/2)=O(n2/2)=O(n2)O(n(n + 1)/2) = O(n^2/2 + n/2) = O(n^2/2) = O(n^2) 

såsom du antagit. 

Marx 284
Postad: 27 feb 2020 21:09
SeriousCephalopod skrev:

Frågan är egentligen lite wonky eftersom en algoritm som gör detta kan vara sämre än O(n^2). En algoritm kan trots allt inte definieras av vad den producerar (listan) utan endast hur den gör detta.

Men om man tar det på allvar att det tar "ett bearbetningsteg att ta fram" ett element så blir komplexiteten samma som antalet sådana oordnade par dvs

O(n(n+1)/2)=O(n2/2+n/2)=O(n2/2)=O(n2)O(n(n + 1)/2) = O(n^2/2 + n/2) = O(n^2/2) = O(n^2) 

såsom du antagit. 

Ja, då fattar jag vad de menade med uppgiften. Tack!

Svara Avbryt
Close