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

Hur många par blir det? 

Marx Online 175
Postad: 27 feb 2020 Redigerad: 27 feb 2020
Laguna skrev:

Hur många par blir det? 

Blir antalet bearbetningssteg  n(n+1)2?

SeriousCephalopod 2078
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 Online 175
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