Miért O (n*log (n) ) a futásidő itt?
Figyelt kérdés
Nem inkább O(n) + amennyi a sorbarendezéshez kell?
A lényeg a fractionalKnapsack függvényben van, amiben igazából csak a sort és a for ciklus a befolyásoló tényező
A for ciklus O(n) és még ehhez jön a sort-hoz szükséges idő,ami kérdéses hogy mennyi, de nem látom miért lenne O(n*log(n)) a teljes program futásideje
2017. dec. 9. 18:26
1/3 anonim 
válasza:
válasza:A sort() eleve elvisz O(n*log(n)) időt. Utána már hiába van O(n) extra lépés, a sort() lesz a domináns az egész függvényből futásidő szempontjából.
2/3 anonim válasza:
válasza:Mivel a rendezés O(n*log(n)), így ez határozza meg a teljes algoritmus komplexitását.
O(n) + O(n*log(n)) = O(n*log(n))
és pl az is igaz, hogy O(1) + O(n) = O(n)
3/3 A kérdező kommentje:
aha,így már világos,köszönöm
2017. dec. 9. 19:19
További kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!