[Powered by Google Translate] Tommy: Le të bëjmë një vështrim në lloj të përzgjedhjes, një algoritmi
për të marrë një listë të numrave dhe zgjidhja e tyre.
Një algoritëm, mbani mend, është thjesht një hap-pas-hapi
Procedura për kryerjen e një detyre.
Ideja themelore prapa përzgjedhjes lloj është për të ndarë
Lista e jonë në dy pjesë -
një pjesë të renditura dhe një pjesë unsorted.
Në çdo hap të algorithm, një numër i është lëvizur nga
Pjesa unsorted në pjesën renditura derisa përfundimisht
Lista e tërë është renditura.
Kështu që këtu është një listë e gjashtë numrave -
23, 42, 4, 16, 8, dhe 15.
Tani për tani lista është konsideruar gjithë Unsorted.
Edhe pse një numër si 16 Maj tashmë të jetë në korrekt i saj
vendndodhjen, algorithm tonë nuk ka asnjë mënyrë për të ditur se deri në
Lista e tërë është renditura.
Pra, ne do të konsiderojmë çdo numër të Unsorted deri ne lloj
ajo veten.
Ne e dimë se ne duam lista të jetë në ngjitje qëllim.
Pra, ne do të duan për të ndërtuar pjesën e renditura të listës sonë
nga e majta në të djathtë, më të vogël tek më i madhi.
Për ta bërë këtë, ne do të duhet për të gjetur elementin minimal Unsorted
dhe e vuri atë në fund të pjesës renditura.
Që nga kjo listë nuk është e renditur, e vetmja mënyrë për të bërë këtë është që të
shikojmë në çdo element në pjesën Unsorted, duke kujtuar
cili element është i ulët dhe krahasimin e
çdo element për këtë.
Pra, ne do të shikojmë të parë në 23.
Ky është elementi i parë që ne kemi parë, kështu që ne do të kujtojmë
atë si minimum.
Ardhshëm ne do të shikojmë në 42.
42 është më e madhe se 23, kështu që 23 është ende minimale.
Tjetra është 4 e cila është më pak se 23, kështu që ne do të kujtojmë 4
si minimum të ri.
Tjetra është 16 e cila është më e madhe se 4, kështu që 4
është ende minimale.
8 është më e madhe se 4 dhe 15 është më e madhe se 4, kështu që duhet të jetë 4
elementi më i vogël unsorted.
Pra, edhe pse si njerëzit mund të shohë menjëherë se është 4
elementi minimal, algorithm ynë ka nevojë të shohim në
çdo element unsorted, edhe pasi kemi gjetur 4 -
element minimale.
Pra, tani që ne kemi gjetur elementin minimal, 4, ne do të duam
për të lëvizur atë në pjesën e renditura të listës.
Që ky është hapi i parë, kjo do të thotë që ne duam të vënë në 4
fillimi i listës.
Tani për tani 23 është në fillim të listës, në mënyrë
le të bie në ujdi 4 dhe 23.
Deri tani lista jonë duket si ky.
Ne e dimë se 4 duhet të jenë në vendin e saj përfundimtare, sepse ajo është
si elementi më i vogël dhe elementi në fillim
nga lista.
Pra, kjo do të thotë që ne kurrë nuk duhet të lëvizin atë përsëri.
Pra, le të përsëris këtë proces për të shtuar një element të
pjesë të renditura nga lista.
Ne e dimë se ne nuk kemi nevojë të shikojmë në 4, për shkak se është
renditura tashmë.
Kështu që ne mund të fillojnë në 42, të cilat ne do të kujtohet si
element minimale.
Kështu që herën tjetër ne do të shikojmë në të 23 i cili është më pak se 42, kështu që ne
kujtohet 23 është minimumi i ri.
Tjetra ne shohim 16 e cila është më pak se 23, në mënyrë që
16 është minimumi i ri.
Tani ne shikojmë në 8 që është më pak se 16, në mënyrë që
8 është minimumi i ri.
8 Dhe në fund është më pak se 15, kështu që ne e dimë se është një minimum 8
element unsorted.
Kështu që do të thotë ne duhet të append 8 të renditura
pjesë e listës.
Tani për tani 4 është elementi zgjidhet vetëm, kështu që ne duam të zhvillohet
8 tej në 4.
Që nga 42 është elementi i parë në pjesën Unsorted e
lista, ne do të duan të bie në ujdi 42 dhe 8.
Deri tani lista jonë duket si ky.
4 dhe 8 përfaqësojnë pjesën renditura e lista, dhe
Numrat e mbetura përfaqësojnë unsorted
pjesë e listës.
Pra, le të vazhdojmë me një tjetër përsëritje.
Ne fillim me 23 këtë kohë, pasi ne nuk kemi nevojë të shohim në
e 4 dhe 8 më, sepse ata kanë
tashmë janë të renditura.
16 është më pak se 23, kështu që ne do të kujtojmë
16 si minimum të ri.
16 është më pak se 42, por 15 është më pak se 16, kështu që duhet të jetë 15
elementi minimal unsorted.
Pra, tani ne duam të bie në ujdi 15 dhe 23 të
na jep këtë listë.
Pjesa renditura e listës përbëhet nga 4, 8 dhe 15, dhe
këto elemente janë Unsorted ende.
Por kjo ndodh pikërisht kështu që elementi tjetër unsorted, 16,
është renditur tashmë.
Megjithatë, nuk ka asnjë mënyrë për të algorithm tonë për të dini se 16
tashmë është në vendin e tij të saktë, kështu që ne ende nevojë për të
përsëritur pikërisht procesin e njëjtë.
Pra, ne shohim se është më pak se 16 42, dhe 16 është më pak se 23, në mënyrë që
16 duhet të jetë element minimale.
Është e pamundur të bie në ujdi me këtë element në vetvete, kështu që ne mund të
thjesht lënë atë në këtë vend.
Pra, ne kemi nevojë të kalojë një shumë të algorithm tonë.
42 është më e madhe se 23, 23 kështu duhet të jetë
element minimale unsorted.
Pasi ne bie në ujdi 23 dhe 42, ne fund me finale tonë
Lista e renditura -
4, 8, 15, 16, 23, 42.
42 Ne e dimë se duhet të jetë në vendin e duhur pasi kjo është e
Elementi i vetëm u largua, dhe kjo është lloj përzgjedhje.
Le tani formalizojë algorithm tonë me disa
pseudokod.
On line një, ne mund të shohim se ne kemi nevojë për të integruar mbi
çdo element i listës.
Përveç element i fundit, pasi elementi 1
Lista është renditur tashmë.
On line dy, ne e konsiderojmë elementin e parë të unsorted
pjesë e listës të jetë minimale, siç bëmë me tonë
Për shembull, kështu që ne kemi diçka për të krahasuar të.
Line tre fillon një lak të dytë në të cilën ne iterate mbi
çdo element unsorted.
Ne e dimë se pas kam iterations, pjesa renditura
e listës sonë duhet të ketë elemente i në atë që çdo hap
llojet një element.
Pra, elementi i parë unsorted duhet të jetë në pozitë që unë plus 1.
On line katër, ne krahasojmë elementin aktuale në minimum
element që kemi parë deri tani.
Nëse elementi i tanishëm është më i vogël se minimumi
element, atëherë ne kujtojmë elementin e tanishme si e re
minimale on line pesë.
Së fundi, në linjat e gjashtë dhe shtatë, ne bie në ujdi minimum
Elementi me elementin e parë Unsorted, duke
duke shtuar se në pjesën e renditura të listës.
Pasi ne kemi një algoritmi, një pyetje e rëndësishme që të kërkoni
veten si programuesit është se sa kohë ka që marrin?
Ne do të pari shtrohet pyetja se sa kohë do të marrë për këtë
algorithm për të kandiduar në rastin më të keq?
Kujtoj ne përfaqësojmë këtë drejtimin
Ora me simbol Big O.
Në mënyrë që të përcaktojë elementin minimal Unsorted, ne
në thelb duhej të krahasojnë çdo element në listë për
çdo element tjetër në listë.
Intuitive, kjo tingëllon si një O e operimit n katror.
Kërkim në pseudokod tonë, ne gjithashtu kemi një lak mbivendosur brenda
tjetër loop, e cila me të vërtetë tingëllon si një O
e veprimit n katror.
Megjithatë, mos harroni se ne nuk duhet të shohim mbi
Lista e të gjithë kur përcaktohet elementin minimal Unsorted?
Pasi ne e dinim se ishte 4 renditura, për shembull, ne nuk
duhet të shohim në atë përsëri.
Pra, e bën këtë më të ulët kohë running?
Për listën tonë të gjatësisë 6, kemi nevojë për të bërë pesë
krahasimet për elementin e parë, katër krahasimet për
elementi i dytë, dhe kështu në.
Kjo do të thotë se numri i përgjithshëm i hapave është shuma e
integers nga 1 deri në gjatësinë e listës minus 1.
Ne mund të përfaqësojë këtë me një mbledhje.
Ne nuk do të shkojë në summations këtu.
Por rezulton se kjo përmbledhje është e barabartë me n herë
n minus 1 mbi 2.
Ose ekuivalente, n katror mbi 2 minus n mbi 2.
Kur flasim për kohën e duhur asymptotic, ky term n katror
do të dominojnë këtë term n.
Pra, zgjedhja është lloj O n katror.
Kujtojnë se në shembullin tonë, lloj përzgjedhje ende e nevojshme për të
kontrolloni nëse një numër që është renditur tashmë
nevojshme për të lëvizur.
Kështu që do të thotë se në qoftë se ne u lloj përzgjedhje mbi një tashmë
renditura listë, ajo do të kërkojë të njëjtin numër hapash si ajo
do kur drejtimin mbi një listë krejtësisht Unsorted.
Pra, ka një lloj përzgjedhje performancën më të mirë rastin e n katror,
që ne përfaqësojmë me omega n katror.
Dhe kjo është ajo për lloj përzgjedhjes.
Vetëm një nga algoritme shumë ne mund të
përdorin për të zgjidhur një listë.
Emri im është Tommy, dhe kjo është CS50.