Marx är nöjd med hjälpen!
Marx 108
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 7663
Postad: 27 feb 2020

Hur många par blir det? 

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

Hur många par blir det? 

Blir antalet bearbetningssteg  n(n+1)2?

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 108
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