Marx är nöjd med hjälpen
Marx 283
Postad: 27 feb 2020

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 13457
Postad: 27 feb 2020

Hur många par blir det? 

Marx 283
Postad: 27 feb 2020 Redigerad: 27 feb 2020
Laguna skrev:

Hur många par blir det? 

Blir antalet bearbetningssteg  n(n+1)2?

SeriousCephalopod 2155
Postad: 27 feb 2020

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 283
Postad: 27 feb 2020
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