Beräkna tidskomplexiteten för en given algoritm
Hej, jag har gjort en uppgift som lyder:
Anta följande algoritm i pseudokod, där A är en array,
for i = 0 until n-1
s = i
for k = s+1 until n
if A[k] > A[s]
s = k
swap(A[s], A[i])
Vilken tidskomplexitet har algoritmen? Motivera/redogör för ditt svar.
Där mitt svar var:
Svar: n+n^2
Motivering: Yttre loopen går från i=0 till antal element i arrayen-1 vilket kan avrundas till att den går genom n antal. Innuti denna har vi en konstant operation först, då är vi på n(1+...). sen har vi en till loop som går genom ca n gånger, och innuti denna har vi endast en konstant operation, då är vi på n(1+n(1)...) slutligen har vi ännu en konstant operation innanför den yttre loopen, vilket ger n(1+n*1+1) som ger 2n+n^2. Tvåan är enbart en konstant, så avrundning ger n+n^2.
Min fråga är:
Jag fick 2/2 poäng på uppgiften men jag undrar om jag verkligen har gjort helt rätt, räknas inte if satsen också som en konstant operation (= 1)? Dvs borde jag inte ha skrivit n(1+n*(1+1)+1) som ger n(2+2n)=2n + 2n^2 där tvåorna enbart är konstanter så det ger n+n^2?
(Det ger förvisso samma svar fast vill inte göra fel)
Tacksam för hjälp!
Möjligtvis förstår jag inte hur du kunde få full poäng för n + n^2 när n^2 hade varit ett lämpligare svar.
Algortitmen ser ut som en försämrad version av bubble sort.
I praktiken är swap-operationen i många hårdvaruimplementationer en operation med högre komplexitet än en call-if-operation så är inte så giltigt att räkna dem som jämlika -- men om vi gör det så kan vi räkna såhär:
Om man räknarantalet if-kontroller (och until avser < snarare än <=) så tycker jag att det är
(n - 1) + (n - 2) + ... + 3 + 2 + 1 = (n - 1)n/2
vilket kan beräknas explicit med aritmetisk summa.
Räknar man antalet swap-operationer så är det n - 1
Så
n(n - 1)/2 + (n - 1)
Vi kan fortsätta att lägga till operationer till räkningen men i slutändande kommer det fortfarande att vara ett 2:a-gradpolynom så komplexiteten kommer bli n^2.
SeriousCephalopod skrev:Möjligtvis förstår jag inte hur du kunde få full poäng för n + n^2 när n^2 hade varit ett lämpligare svar.
Algortitmen ser ut som en försämrad version av bubble sort.
I praktiken är swap-operationen i många hårdvaruimplementationer en operation med högre komplexitet än en call-if-operation så är inte så giltigt att räkna dem som jämlika -- men om vi gör det så kan vi räkna såhär:
Om man räknarantalet if-kontroller (och until avser < snarare än <=) så tycker jag att det är
(n - 1) + (n - 2) + ... + 3 + 2 + 1 = (n - 1)n/2
vilket kan beräknas explicit med aritmetisk summa.
Räknar man antalet swap-operationer så är det n - 1
Så
n(n - 1)/2 + (n - 1)
Vi kan fortsätta att lägga till operationer till räkningen men i slutändande kommer det fortfarande att vara ett 2:a-gradpolynom så komplexiteten kommer bli n^2.
Förstår ditt resonemang. Tack så mycket för förklaringen.
