[Powered by Google Translate] Ön valószínűleg hallott az emberek beszélnek a gyors és hatékony algoritmus
végrehajtására az adott feladat,
de hogy pontosan mit jelent ez egy olyan algoritmust, hogy gyors vagy hatékony?
Nos, ez nem beszél a mérés valós időben,
mint a másodperc vagy perc.
Ez azért van, mert számítógépes hardver
és a szoftver változik drasztikusan.
A program esetleg lassabban futnak, mint a tiéd,
mert én fut egy régebbi számítógép,
vagy azért, mert megtörténhet, hogy játszik egy online videojáték
ugyanakkor, amely domborító All My memória,
vagy talán fut a programom a különböző szoftverek
, amely összeköttetésben van a készülék különböző alacsony szinten.
Ez olyan, mint összehasonlítása alma és a narancs.
Csak azért, mert a lassabb számítógépen hosszabb időt vesz igénybe
, mint a tiéd, hogy adja vissza a választ
nem jelenti azt, hogy a hatékonyabb algoritmust.
>> Szóval, mivel nem tudjuk közvetlenül összehasonlítani a Runtimes programok
másodpercben vagy percben,
hogyan hasonlítsa össze 2 különböző algoritmusok
függetlenül attól, hogy hardver vagy szoftver környezetben?
Ahhoz, hogy hozzon létre egy egységes módon mérésének algoritmikus hatékonyság,
számítógép tudósok és matematikusok kidolgozott
koncepciók mérésére aszimptotikus bonyolultsága program
és a jelölés az úgynevezett "Big Ohnotation"
leírására ezt.
A hivatalos meghatározás szerint a függvény f (x)
fut a sorrendben g (x)
ha létezik valami (x) érték, x ₀ és
bizonyos konstans, C, amelyek
f (x) kisebb vagy egyenlő, mint
hogy állandó szor g (x)
minden x-nél nagyobb x ₀.
>> De ne félj elérhető a hivatalos meghatározás.
Mit jelent ez valójában azt jelenti, a kevésbé elméleti szempontból?
Nos, ez alapvetően egy módja elemzése
milyen gyors a program futásidejű nő aszimptotikusan.
Azaz, mivel a méret a bemenetek felé növekszik végtelen,
azt mondják, te válogatás tömb mérete 1000 képest egy sor 10-es méret.
Hogyan futási a programunk nő?
Képzeljük el például, számítva a karakterek száma
egy string a legegyszerűbb módon
gyalog az egész szöveg
levél-by-levél és hogy 1 a számláló minden egyes karakter.
Ez az algoritmus azt mondta, hogy fut a lineáris időben
tekintetében a karakterek száma,
'N' a string.
Röviden, ez fut O (n).
Miért van ez?
Nos, ezt a módszert, a szükséges időt
áthalad a teljes szöveg
arányos a karakterek számát.
Számlálása a karakterek száma a 20-karakterlánc
fog tartani az kétszer mivel addig, amíg
számolni a karaktereket a 10-karakterlánc,
mert meg kell nézni az összes karakter
és minden karakter úgy ugyanannyi időt, hogy nézd meg.
Ahogy növeli a karakterek száma,
a futásidejű növeli lineárisan a bemenet hosszát.
>> Most képzeld el, ha úgy dönt, hogy a lineáris idő,
O (n), csak nem volt elég gyors az Ön számára?
Talán tárolására hatalmas húrok,
, és nem engedheti meg magának az extra időt venne
áthalad minden a karakter számít egy-az-egy.
Szóval, úgy dönt, hogy megpróbál valami mást.
Mi lenne, ha történne már tárolni a karakterek száma
A húr, mondjuk, egy változó úgynevezett "len"
korai szakaszában a program,
mielőtt még tárolja a legelső karakter a szöveg?
Aztán csak annyit kéne tenni most, hogy megtudja, a húr hossza,
van ellenőrizni, hogy milyen az értéke a változó.
Ugye nem kell nézni a string maga egyáltalán,
és nyissa meg a változó értékét, mint a len tekinthető
egy aszimptotikusan konstans idejű működés,
vagy O (1).
Miért van ez? Nos, emlékszem, milyen aszimptotikus komplexitás jelent.
Hogyan működik a futási változás a méret
a bemenetek nő?
>> Mondja el, hogy akarták, hogy a karakterek száma egy nagyobb string.
Nos, ez nem számít, milyen nagy legyenek a húr,
még egy millió karakter hosszú,
csak annyit kéne tennie, hogy megtalálja a string hosszának ezzel a megközelítéssel,
hogy felolvassa az érték a változó len,
amit már elért.
A bemeneti hossz, azaz a string hossza akarsz találni,
nem érinti egyáltalán milyen gyors a program fut.
Ez a része a program fut egyformán gyors egy karakterlánc
és ezer-karakterlánc,
és ez az, amiért ezt a programot a továbbiakban mint fut konstans id
tekintetében a bemeneti méret.
>> Persze, van egy hátránya.
Töltesz extra memóriát a számítógépen
tárolására a változó
és az extra időt, akkor
tenni a tényleges tárolása változó,
de a lényeg még mindig fennáll,
kideríteni, milyen hosszú a karakterlánc
nem függ a hossza a húr egyáltalán.
Szóval, ez fut O (1) vagy konstans időt.
Ez természetesen nem jelenti
hogy a kód fut 1 lépés,
de nem számít, hogy hány lépés van,
ha nem változik a mérete a bemenet,
ez még mindig aszimptotikusan konstans, amely az általunk képviselt, mint O (1).
>> Mint tudod talán kitalálni,
sok különböző nagy O Runtimes mérésére algoritmusok.
O (n) ² algoritmusok aszimptotikusan lassabb, mint O (n) algoritmusok.
Azaz, mivel az elemek száma (n) nő,
végül O (n) ² algoritmusok több időre lesz szükség
mint O (n) algoritmusok futtatására.
Ez nem azt jelenti, O (n) algoritmusok mindig fut gyorsabban
mint O (n) ² algoritmusok, még ugyanabban a környezetben,
ugyanazon a hardveren.
Lehet, hogy a kis méretű input,
az O (n) ² algoritmus meglehet ténylegesen munkát gyorsabban,
de, végül, mivel a bemeneti méret növekszik
felé végtelen, az O (n) ² algoritmus a futási
végül oltja a futásidejű az O (n) algoritmus.
Mint minden kvadratikus matematikai függvény
végül előzni minden lineáris függvény,
nem számít, hogy mennyi egy fej kezdeni a lineáris függvény indul.
Ha dolgozik a nagy mennyiségű adat,
algoritmusok futnak O (n) ² idő tényleg végén lassul a program,
de a kis méretű input,
akkor valószínűleg észre sem.
>> További aszimptotikus összetettség,
logaritmikus idő, O (log n).
Egy példa egy algoritmus, hogy fut ilyen gyorsan
a klasszikus bináris keresés algoritmus,
megállapításának egyik eleme, egy már rendezett lista elemeit.
>> Ha nem tudja, mi a bináris keresést tesz,
Majd elmondom neked nagyon gyorsan.
Tegyük fel, hogy keres a 3-as szám
e tömb egészek.
Úgy tűnik, a középső elem a tömb
és megkérdezi: "Van az elemet szeretnék nagyobb, egyenlő vagy kisebb, mint ez?"
Ha ez egyforma, akkor nagyszerű. Megtalálta az elem, és kész.
Ha ez nagyobb, akkor tudja az elemet
kell lennie a jobb oldalon a tömb,
és akkor csak nézd meg, hogy a jövőben,
és ha ez kisebb, akkor tudod, hogy kell, hogy legyen a bal oldalon.
Ez a folyamat azután megismételjük a kisebb méretű tömb
amíg a helyes elem található.
>> Ez a nagy teljesítményű algoritmus csökkenti a tömb mérete fél minden művelet.
Tehát találni egy eleme a rendezett tömb mérete 8,
legfeljebb (log ₂ 8),
vagy 3 E műveletek,
ellenőrzése a középső elem, akkor a vágás a tömb ketté lesz szükség,
mivel a tömb mérete 16 előnyben (log ₂ 16),
vagy 4 műveletek.
Ez csak 1 további művelet kétszeres méretű tömb.
Megkettőzése a méret a tömb
növeli a futási csak 1 darab ezt a kódot.
Ismét ellenőrzése középső eleme a listából, majd felosztása.
Szóval, azt mondják, hogy működik logaritmikus időben,
O (log n).
De várjunk csak, azt mondod,
nem ez attól függ, a listában az elem, amit keresett?
Mi van, ha az első elem nézel történik, hogy az igazit?
Aztán, csak úgy 1 működését,
nem számít, milyen nagy a lista.
>> Nos, ezért számítógépes szakemberek több szempontból
az aszimptotikus komplexitás, melyek tükrözik a legjobb eset
és a legrosszabb teljesítményt az algoritmus.
További megfelelően, a felső és alsó határ
A futás közben.
A legjobb esetben a bináris keresés, a mi elem
ott a közepén,
és megkapod azt a konstans időben,
nem számít, milyen nagy a többi tömb.
A szimbólum erre a célra használt Ω.
Szóval, ez az algoritmus azt mondta, hogy fut Ω (1).
A legjobb esetben azt állapítja meg, az elem gyorsan,
nem számít, milyen nagy a tömb,
de a legrosszabb esetben,
azt elvégezni (log n) osztott ellenőrzések
a tömb, hogy megtalálja a megfelelő elemet.
Worst-case felső határt említi a nagy "O", hogy már tudod.
Szóval, ez O (log n), de Ω (1).
>> A lineáris keresés, ezzel szemben,
területén, ahol Ön séta minden elemét a tömb
hogy megtalálja a kívánt,
a legjobb esetben Ω (1).
Ismét az első elem akarsz.
Szóval, nem számít, milyen nagy a tömb.
A legrosszabb esetben, ez az utolsó elem a tömbben.
Szóval, meg kell járni az összes n elem a tömbben, hogy megtalálja azt,
szeretném, ha kerestek a 3.
Szóval, ez fut O (n) idő
mert ez arányos az elemek száma a tömbben.
>> Még egy jel használt Θ.
Ezt felhasználhatjuk leírására algoritmusok ahol a legjobb és legrosszabb esetben
azonosak.
Ez a helyzet a string-length algoritmusok beszéltünk korábban.
Azaz, ha tárolja változó előtt
tároljuk a húr és a hozzáférést később állandó időben.
Nem számít, milyen szám
vagyunk tárolja, hogy változó, akkor meg kell nézni.
A legjobb eset az, hogy nézd meg
és keresse meg a hosszát a húr.
Szóval Ω (1) vagy legjobb esetben konstans idő.
A legrosszabb eset az,
nézzük, és megtalálni a hossza a húr.
Szóval, O (1) vagy konstans idő legrosszabb esetben.
Így, mivel a legjobb és legrosszabb esetek az ugyanaz,
ezt lehet mondani, hogy futtatni Θ (1) idő.
>> Összefoglalva, van jó módja, hogy ok kódokról hatékonyság
ismerete nélkül semmit a valós idejű vesznek futtatni,
által érintett sok külső tényezők,
beleértve a különböző hardver, szoftver,
vagy a sajátosságait a kódot.
Azt is lehetővé teszi számunkra, hogy érvelni is arról, hogy mi fog történni
, ha a méret a bemenetek növekszik.
>> Ha fut O (n) ² algoritmus,
vagy ami még rosszabb, egy O (2 ⁿ) algoritmus,
az egyik leggyorsabban növekvő típusokat,
akkor tényleg elkezdi észrevenni a lassulás
ha elkezd dolgozni nagyobb mennyiségű adat.
>> Ez aszimptotikus komplexitás. Kösz.