Algoritmanalys (antal operationer) har prov om 3 dagar fattar ingenting
Hej jag håller på att bryta ihop i vår lärobok står ingenting om algoritmanalys och jag känner mig helt lost.
Vi har prov där vi ska kunna räkna antal operationer i bästa värsta fall.
Kan någon snälla hjälpa mig förstå om man har pseudokod som tex:
Algorithm arrayMax(A,n)
input: An array A storing n integers
output: The maximum element in A
currentMax <- A[0] //1+1 operationer
for i <- 1 to n-1 do //1+n(1+1)+(n-1)*([]+1) operationer
if currentMax < A[i] then //1+1+1
currentMax <- A[i] //1+1
return currentMax //1
Tmax(n)= 3+2n+(n-1)*6 +1 = 8n-2 värsta fall
Tmin(n)= 3+2n+(n-1)*4 +1 = 6n bästa fall
hur ska man tänka? jag förstår ingenting av loopen. Kan någon som gjort detta gå igenom stegvis vad som händer när loopar finns och varför en if sats blir 1+1+1 när en tilldelning blir 1+1. och hur allt läggs ihop sen och hur man ska tänka i det generella fallet vid loopar och dess olika jämförelser + hur man ska tänka överlag jag skulle vara så oerhört tacksam för någon hjälp känns oerhört tungt just nu och våra handledare är borta till efter provet. Tack på förhand
- Tilldelningsraderna (som currentMax <- A[0]) innehåller 1 "läsning ur array" + 1 tilldelning, dvs 2 operationer.
- If-raderna innehåller utläsning ur array, jämförelse och själva if-satsen, dvs 3 operationer.
- For-loopen har 1 inledande tilldelning, en utläsning och en jämförelse per iteration plus en inkrementering per iteration utom den sista. Måste erkänna att jag inte förstår notationen []+1.
- I bästa fall behöver du bara tilldela currentMax 1 gång (om A[0] är maxvärdet), i värsta fall måste du göra det n gånger (om arrayen är strikt växande)
Hoppas att det gav viss klarhet
jaha så den räknar operationen + antal varv i loopen n ggr. och adderar med den andra operationen + varv. Tusen tack nu förstår jag bättre. bättre förklaring än ngn lärare kunnat ge. Är det då så att en nästlad loop multipliceras med varandra och då oftast producerar n^2 operationer typ?
tusen tack för hjälpen! det uppskattas verkligen
Nästlade loopar gör ofta ett kvadratiskt ntal operationer:
for i = 1 to n
for j = 1 to n
s = s+j
t. ex.
