Najdłuższe/najkrótsze działanie algorytmu

Question

Witam, mam podać przykładowe dane dla których algorytm zapisany w pythonie będzie działał najdłużej i najkrócej. Na początku myślałem że jeśli wszystkie dane będą równe R to kod będzie działał najdłużej(np: R=10,n=5,r=[10,10,10,10,10]) a dla danych mniejszych od R najkrócej (np R=10, n=5,r=[5,4,3,2,1]) ale zauważyłem że w drugim przypadku pętla nie potrzebnie wykonuje operacje ponieważ wszystkie dane w r zostały już sprawdzone i już zgłupiałem i nie wiem czy nie powinno być na odwrót.

Dodatkowo nie mogę zmodyfikować algorytmu gdyż mam właśnie na jego podstawie wykonać prezentację.

Opis algorytmu:

Załóżmy, że mamy dowolnie dużą liczbę pudełek, każde o rozmiarze R, oraz n przedmiotów o rozmiarach r[1],r[2],…r[n][1],[2],…[]. Zakładamy, że R≥r[1]≥r[2]…≥r[n]≥[1]≥[2]…≥[].

Mamy włożyć przedmioty do pudełek, co najwyżej dwa do jednego pudełka.

Algorytm:

wynik := n;
for i := 1 to n do 
  if (i  <  wynik and r[i]+r[wynik] <= R) 
    wynik := wynik-1;

Kod:

R=10
n=5
r=[5,4,4,3,2]


wynik=n
for i in range(n):
    if(i<wynik-1 and r[i]+r[wynik-1] <= R):
        wynik=wynik-1
print(wynik)

Nie wiem czy czasami nie ma "najszybszych/najdłuższych" danych ponieważ długość działania pętli jest uzależniona przez n więc dla jakich kolwiek r[n] algorytm będzie się wykonywał n razy

Comments

Może o czasie wykonywania się algorytmu decyduje to, czy będzie sprawdzane “r[i] + r[wynik] <= R” oraz czy wykona się linia “wynik := wynik - 1;”. W takim razie nie miałoby sensu zliczanie powtórzeń pętli.

Przy takim opisie algorytm działałby najkrócej dla takich danych, które najszybciej doprowadzają do spełnienia warunku “i == wynik”, czyli dla takich danych, które powodują za każdym razem wykonanie się warunku “r[i] + r[wynik] <= R” i zmierzanie zmiennej “wynik” w dół do spotkania z “i”.

A najdłużej działałby dla takich danych, które jak najwięcej razy nie pozwalają na spełnienie warunku “r[i] + r[wynik] <= R”, by był sprawdzany do końca wykonywania się pętli.

Pozostaje jeszcze uwzględnienie kosztu wykonywania linii “wynik := wynik - 1;”.

I nie wiem, dlaczego zmieniłeś warunki w kodzie Pythona względem pseudokodu.

---

Pseudokod dostałem od nauczyciela i na jego podstawie mam opisać algorytm

---

Tylko że w kodzie Pythona jest sprawdzanie warunków względem “wynik - 1”, a w pseudokodzie względem “wynik”.

W każdym razie jeśli warunek “r[i] + r[wy­nik] <= R” potraktujesz jako instrukcję konieczną do wykonania, gdy “i < wynik”, to wtedy masz czas wykonywania się algorytmu.