[Powered by Google Translate] Vostè probablement ha sentit parlar d'un algoritme ràpid o eficient
per a l'execució de la seva tasca en particular,
però què significa això per a un algorisme per ser ràpid o eficient?
Bé, no està parlant d'un mesurament en temps real,
com segons o minuts.
Això es deu a maquinari informàtic
i pot variar dràsticament.
El meu programa pot córrer més lent que el teu,
perquè ho estic corrent en un ordinador antic,
o perquè se m'acut estar jugant un joc de vídeo en línia
al mateix temps, que està acaparant tot el meu memòria,
o podria estar corrent el meu programa a través de diferents programes
que es comunica amb la màquina de manera diferent en un nivell baix.
És com comparar pomes i taronges.
El fet que el meu equip més lent triga més
que el teu per tornar una resposta
no vol dir que vostè té l'algorisme més eficient.
>> Per tant, ja que no es pot comparar directament els temps d'execució dels programes
en qüestió de segons o minuts,
Com podem comparar dos algorismes diferents
independentment del seu maquinari o l'entorn del programari?
Per crear una forma més uniforme de mesurament de l'eficiència algorísmica,
els informàtics i matemàtics han ideat
conceptes per a la mesura de la complexitat asimptòtica d'un programa
i una notació anomenada "Ohnotation Big '
per descriure això.
La definició formal és que una funció f (x)
s'executa en l'ordre de g (x)
si existeix algun valor (x), x ₀ i
alguna constant C, per a això
f (x) és menor que o igual a
aquesta constant g vegades (x)
per a tot x major que x ₀.
>> Però no s'espanten per la definició formal.
Què significa això en realitat significa en termes menys teòrics?
Bé, és bàsicament una forma d'analitzar
la rapidesa d'execució d'un programa creix asimptòticament.
És a dir, com la mida de les entrades augmenta cap a l'infinit,
Escolta, estàs ordenar una matriu de mida 1000 en comparació amb una matriu de mida 10.
Com afecta el temps d'execució del seu programa de créixer?
Per exemple, imaginar comptant el nombre de caràcters
en una cadena de la forma més senzilla
caminant a través de tota la cadena
lletra per lletra i afegint 1 a un comptador per a cada caràcter.
Aquest algorisme es diu que s'executen en temps lineal
pel que fa al nombre de caràcters,
'N' a la cadena.
En resum, s'executa en O (n).
Per què és això?
Així, amb aquest mètode, el temps requerit
per travessar la cadena completa
és proporcional al nombre de caràcters.
Comptar el nombre de caràcters d'una cadena de 20 caràcters
es va a prendre el doble de temps que sigui necessari
per comptar els caràcters d'una cadena de 10 caràcters,
perquè cal mirar tots els personatges
i cada personatge té la mateixa quantitat de temps per mirar.
A mesura que augmenta el nombre de caràcters,
el temps d'execució s'incrementarà linealment amb la longitud d'entrada.
>> Ara, imagini si vostè decideix que el temps lineal,
O (n), simplement no era prou ràpid per a tu?
Potser vostè està emmagatzemant enormes cadenes,
i vostè no pot pagar el temps extra que tindria
per recórrer la totalitat dels seus caràcters de comptatge un per un.
Per tant, vostè decideix intentar alguna cosa diferent.
Què passaria si a emmagatzemar i el nombre de caràcters
a la cadena, per exemple, en una variable anomenada 'llengua'
des del principi en el programa,
fins i tot abans d'emmagatzemar el primer caràcter en la cadena?
Llavors, l'únic que hauria de fer ara per esbrinar la longitud de la cadena,
és comprovar quin és el valor de la variable és.
No ha de mirar la mateixa cadena en absolut,
i accedir al valor d'una variable com llengua es considera
un temps asimptòticament constant operació,
o O (1).
Per què és això? Bé, recordes el que significa complexitat asimptòtica.
Com canvia el temps d'execució com la mida
de les seves entrades creix?
>> Diguem que es tracta d'aconseguir el nombre de caràcters d'una cadena més gran.
Bé, no importa el gran que fer la cadena,
fins a un milió de caràcters de longitud,
Tot el que has de fer per trobar la longitud de la corda amb aquest enfocament,
és llegir el valor de la llengua variable,
que ja ha fet.
La longitud de l'entrada, és a dir, la longitud de la cadena que s'està tractant de trobar,
no afecta en absolut la velocitat del seu programa s'executa.
Aquesta part del seu programa funcionaria igual de ràpid en una cadena d'un sol caràcter
i una cadena de mil caràcters,
i és per això que aquest programa s'anomena execució en temps constant
pel que fa a la mida de l'entrada.
>> Per descomptat, hi ha un inconvenient.
Et passes l'espai de memòria addicional en el seu ordinador
emmagatzemar la variable
i el temps extra que el porta
per fer l'emmagatzematge real de la variable,
però el punt segueix en peu,
esbrinar quant de temps la cadena
no depèn de la longitud de la cadena en absolut.
Així, s'executa en O (1) o constant de temps.
Això certament no ha de significar
que el codi s'executa en un pas,
però no importa la quantitat de passos que és,
Si no canvia amb la grandària de les entrades,
tot i així és asimptòticament constant que representem com O (1).
>> Com podran imaginar,
hi ha molts diferents temps d'execució Big O per mesurar amb algorismes.
O (n) ² algoritmes són asimptòticament més lent que O (n) algoritmes.
És a dir, com el nombre d'elements (n) creix,
amb el temps O (n) ² algoritmes prendrà més temps
d'O (n) algoritmes per córrer.
Això no vol dir que O (n) algoritmes sempre s'executen més ràpid
d'O (n) ² algoritmes, fins i tot en el mateix entorn,
en el mateix maquinari.
Potser en mides d'entrada,
l'O (n) ² algorisme podria funcionar més ràpid,
però, amb el temps, ja que la mida d'entrada augmenta
cap a l'infinit, l'O (n) temps d'execució de l'algorisme ²
finalment eclipsarà el temps d'execució de la O (n) algorisme.
Igual que qualsevol funció matemàtica de segon grau
eventualment superarà qualsevol funció lineal,
no importa la quantitat d'un capçal d'iniciar la funció lineal comença amb.
Si està treballant amb grans quantitats de dades,
algoritmes que s'executen en O (n) ² realment pot arribar a alentir el seu programa,
però per mides petits d'entrada,
probablement ni tan sols es donarà compte.
>> Una altra complexitat asimptòtica és,
temps logarítmica, O (log n).
Un exemple d'un algorisme que s'executa aquest ràpidament
és l'algorisme de recerca binària clàssica,
per buscar un element en una llista ja-ordenats d'elements.
>> Si no sap el que fa la recerca binària,
T'ho explicaré perquè realment ràpid.
Diguem que vostè està buscant el número 3
en aquesta matriu d'enters.
Es veu en l'element mig de la matriu
i pregunta: "Està l'element que vull major, igual o menor que això?"
Si és igual, llavors genial. Vostè va trobar l'element, i ja està.
Si és major, llavors vostè sap que l'element
ha d'estar en la part dreta de la matriu,
i només es pot observar que, en el futur,
i si és menor, llavors vostè sap que ha d'estar a la banda esquerra.
Aquest procés es repeteix llavors amb la matriu més petits
fins que l'element es troba el correcte.
>> Aquesta potent algorisme redueix la mida de la matriu a la meitat amb cada operació.
Per tant, per trobar un element en una matriu ordenada de mida 8,
en la majoria (log ₂ 8),
o 3 d'aquestes operacions,
comprovant l'element mitjà, llavors el tall de la matriu en un mitjà es requerirà,
mentre que una matriu de mida 16 té (log ₂ 16),
o 4 operacions.
Això és només una operació més per una sèrie duplicat en grandària.
Doblegant la mida de la matriu
augmenta el temps d'execució només en un 1 tros d'aquest codi.
Un cop més, comprovar l'element central de la llista, i després partir.
Així, es diu que opera en temps logarítmic,
O (log n).
Espereu-vos, vostè diu,
¿Això no depenen del lloc en la llista l'element que està buscant és?
I si el primer element es miri resulta ser la correcta?
Llavors, només es necessita una operació,
no importa què tan gran és la llista.
>> Bé, és per això que els informàtics tenen termes més
la complexitat asimptòtica que reflecteixen el millor dels casos
i en el pitjor dels casos actuacions d'un algorisme.
Més adequadament, els límits superior i inferior
en el temps d'execució.
En el millor dels casos per a la recerca binària, és el nostre element
bell mig,
i vostè ho aconsegueix en temps constant,
no importa el gran que la resta de la matriu és.
El símbol utilitzat per això és Ω.
Per tant, aquest algorisme es diu d'executar en Ω (1).
En el millor dels casos, es troba l'element ràpidament,
no importa què tan gran és la matriu,
però en el pitjor dels casos,
que ha de realitzar (log n) els controls parcials
de la matriu per trobar l'element correcte.
Límits pitjor dels casos superiors s'anomenen amb la gran "O" que vostè ja sap.
Per tant, és O (log n), però Ω (1).
>> Una recerca lineal, per contra,
en el qual a través de cada element de la matriu
per trobar el que voleu,
és en el millor Ω (1).
Un cop més, el primer element que desitgi.
Per tant, tant i fa tan gran és la matriu.
En el pitjor cas, que és l'últim element de la matriu.
Per tant, has de caminar a través de tots els n elements de la matriu per trobar-lo,
com si estigués buscant un 3.
Per tant, s'executa en O (n) temps
perquè és proporcional al nombre d'elements de la matriu.
>> Un símbol més utilitzat és Θ.
Això pot ser usat per descriure els algorismes on els casos millor i pitjor
són els mateixos.
Aquest és el cas dels algorismes de longitud de cadena que parlem abans.
És a dir, si la emmagatzemem en una variable abans
emmagatzemem la cadena i accedir-hi més tard en temps constant.
No importa quin número
estem emmagatzemant en aquesta variable, haurem de mirar.
El cas és que miri
i trobar la longitud de la cadena.
Així Ω (1) o en el millor dels casos la constant de temps.
El pitjor cas és,
ens fixem en ella i trobar la longitud de la cadena.
Així, O (1) o constant de temps en el pitjor cas.
Així, atès que la millor i el pitjor dels casos són els mateixos,
això es pot dir per funcionar en Θ (1) hora.
>> En resum, tenim una bona manera de raonar sobre els codis d'eficiència
sense saber res sobre el temps real que triga a executar,
que es veu afectada per molts factors externs,
incloent maquinari diferents, programari,
o els detalls del seu codi.
A més, ens permet raonar bé sobre el que succeirà
quan la mida dels increments de les entrades.
>> Si s'executa en O (n) ² algorisme,
o pitjor encara, un O (2 ⁿ) algorisme,
un dels més ràpids tipus de cultiu,
que realment començarà a notar la desacceleració
quan comences a treballar amb grans quantitats de dades.
>> Aquesta és la complexitat asimptòtica. Gràcies.