Algoritmus pre maximálne celé číslo v množine celých čísel - algoritmus, mergesort, triedenie bublinami

Ak potrebujeme implementovať funkciu, ktorá mápole celých čísel a vráti maximálne celé číslo v kolekcii, za predpokladu, že dĺžka poľa je menšia ako 1000. Použili by ste triedenie triedenia alebo zlúčenie a prečo?

Čo sa stane s vyššie uvedenou voľbou algoritmu,ak je dĺžka poľa väčšia ako 1000? Som trochu zmätený, prečo by som mal použiť konkrétny algoritmus nad iným. Je to len kvôli jeho zložitosti a času alebo iným faktorom, ktoré sa na tom podieľajú? Čo keď musím vyskúšať vyššie uvedenú funkciu a to trvá oveľa viac času na jednoduchý algoritmus a menej času na komplexný algoritmus?

odpovede:

Ja by som "t triediť vôbec. Ja" d len prejsť pole a sledovať najväčší, ako som ísť. Trvá to čas O (N), zatiaľ čo algoritmy triedenia vo všeobecnosti „nebudú lepšie ako O (N * log (N)).

Táto lokalita skaly

http://www.sorting-algorithms.com/

No, ak MUSÍTE triediť, potom použite druh zlúčeniapretože je to oveľa rýchlejšie ako triedenie bubliniek. Pre 1000 prvkov a jeden druh, ktorý si pravdepodobne nevšimnete, si všimnete rozdielu na modernom počítači, ale pre viac elementov (ja som myslel> = 10 000) sa tento rozdiel stane nemožným.

Umožňuje zavolať dĺžku poľa N.

Triedenie poľa pomocou Bubble Sort trvá zhruba v N * N jednotkách času.

Zoradenie pomocou Merge Sort trvá v poradí N * log N jednotiek času.

Jednoduchý pohľad na každý prvok jeden po druhom a sledovanie toho, ktorý z nich je najväčší, bude mať v poradí N jednotiek času.

Preto použite poslednú metódu.