Az alábbi maximumkeresés a lista elemein iterál: maxval = mylist[0]
for v in mylist:
if v maxval:
maxval = v Milyen nagyságrendű a futásideje a lista n hosszának függvényében, és miért?

Question

Az alábbi maximumkeresés a lista elemein iterál: maxval = mylist[0]
for v in mylist:
    if v > maxval:
        maxval = v Milyen nagyságrendű a futásideje a lista n hosszának függvényében, és miért?

Answer

Logaritmikus, mert minden összehasonlítás után csak a nagyobbik értéket viszi tovább, a kisebbiket elveti.

Answer

Konstans, mert a ciklus végig csak egyetlen értéket tárol, az addig talált legnagyobbat, és ez a lista hosszától nem függ.

Answer

Lineáris, mert minden elemet pontosan egyszer hasonlít össze az addig talált legnagyobb értékkel.

Answer

Négyzetes, mert minden elemet össze kell hasonlítani az összes többi elemmel, hogy kiderüljön, van-e nála nagyobb.

Crowdly

Az alábbi maximumkeresés a lista elemein iterál: maxval = mylist[0] for v in myl...

Want instant access to all verified answers on edu.kozlek.bme.hu?