Beste svaret
Det er ikke noe svar på dette.
La oss finne svaret på denne problemstillingen:
Q. Hvordan finner jeg ut at en algoritme fungerer bedre?
A. Vanligste måter å sammenligne algoritmer på:
1) Tidskompleksitet
2) Romkompleksitet
3) Løsningskvalitet (kanskje ikke være aktuelt hvis det foreslås å løse et problem nøyaktig). Denne kan være en stor faktor hvis vi snakker om tilnærmelsesalgoritmer.
4) Enkel implementering / tilpasning av algoritme. Noen algoritmer kan ha mye overhead å implementere riktig. Det er noen ganger mer passende algoritmer for applikasjonen din. For eksempel, i parallell databehandling, vil de fleste finne Bellman-Ford mer nyttig enn Dijkstras algoritme på grunn av måten Bellman-Ford fungerer på.
Imidlertid er tid og kompleksitet ikke * alltid * ønsket funksjon for å maksimere; Jeg vil gi to eksempler.
Det ene er «numerisk stabilitet» , et trekk ved algoritmer i både lineær algebra og i differensiallikninger. Vi bruker både mer algoritmisk tid og mer algoritmisk kompleksitet på algoritmer som er mer numerisk stabile. I lineær algebra skyldes ustabilitet vanligvis når en algoritme møter tall for nær null eller uendelig eller begge deler, på grunn av den endelige representasjonen av tall, kan oppløsningen gå tapt. Generelt forårsaker dette veldig forskjellige tall, bare noen få epsiloner som er forskjellige fra hverandre (der epsilon er det minste tallet som kan legges til en, på en maskin, og får et resultat! = 1), for å gi store forskjeller i svaret. Så for eksempel bruker vi mye tid og romkompleksitet ved å «svinge» i LU-faktoriseringen for å få en stabil algoritme; uten å svinge LU er ikke stabil. På samme måte har vi algoritmer som ikke gjør annet enn å «kondisjonere» matriser for å unngå ustabilitet.
Et andre eksempel er «robusthet» i dens tekniske statistiske sans. Robusthet betyr et mål eller en algoritme som er * ikke * sensitiv for avvikere. Så for eksempel når jeg tilpasser en minste kvadratlinje til et sett med punkter, kan linjen være sterkt skjev med en enkelt ekstremt stor verdi. Selv om jeg har 99 par tall som danner en perfekt 45 graders linje, hvis jeg legger til et enkelt avvikerpar som Y-verdien er hundre ganger så mye som det «burde» være å falle på samme linje, vil den tilpassede linjen være alvorlig skjev av 45 graders linjen. Algoritmen vil «gi opp» den perfekte passformen for 99 poeng for bedre å representere det ene outlier-punktet. Det er * ikke * robust.
En robust tilnærming med minste kvadrat er, i stedet for å finne linjen som minimerer summen av kvadrerte feil opprettet ved å bruke den linjen, å finne linjen som minimerer * medianen av de kvadratiske feilene som ble opprettet ved å bruke den linjen. I eksemplet er denne linjen 45 graders linje, og medianen av de kvadrerte feilene er null, og det avvikende punktet (og faktisk opptil 98 galere avvikere) vil bli ignorert fullstendig. Linjen på 45 grader ville bli funnet.
Lignende robuste algoritmer eksisterer for å tilpasse statistiske kurver, finne former osv. De er imidlertid kostbare i tid, noen ganger alvorlig. Men tidskostnaden er verdt det fordi robust statistikk effektivt er immun mot «støy» i signaler, der minst kvadratiske feiltilnærminger ikke er. Den virkelige verden er full av både støy og avvik, noen av dem forårsaket av menneskelige eller maskinfeil, spesielt i pikselerte bilder eller samplet lyd. Under slike omstendigheter kan en mer kostnadskrevende robust algoritme finne signaler i et støyende miljø der raskere algoritmer gir svar som er så ødelagt av støy at de er ubrukelige, eller til og med farlige hvis de blir akseptert.
I noen tilfeller, tid og romkompleksitet er ikke så viktig som å finne et svar som mest sannsynlig vil modellere det faktiske signalet til tross for støy og degradering av signalet. for å utføre funksjonsbasert beregning, som kan følges mekanisk. I det funksjonsbaserte matematiske verdensbildet må alle innganger spesifiseres ved starten av beregningen, som fortsetter på lukket måte. Begrepet om en algoritme er iboende uformell, siden en algoritmisk beskrivelse ikke er begrenset til noe enkelt språk eller formalisme.
Det kanskje eldste eksemplet er Euclids algoritme for å finne vanlige delere. Algoritmer fanger opp hva det betyr for en beregning å være «effektiv». I likhet med matematiske formler, forteller algoritmer oss hvordan vi kan beregne en verdi; i motsetning til dem, kan algoritmer involvere det vi nå kaller sløyfer eller grener.
Rollen på algoritmen: Gitt en viss endelig inngangsverdi x, beskriver en algoritme trinnene for effektiv transformasjon av den til en utgangsverdi y, hvor y er f (x) for noen rekursiv funksjon f.
Algoritmer ble adoptert av de tidlige datavitenskapsmennene på 1950-tallet, som laget forbindelsen mellom algoritmer og Turing Machines (TMs, en formell beregningsmodell fra 1936), som likestiller deres uttrykksevne.
Knuths berømte og innflytelsesrike lærebok, «The Art of Computer Programming, Vol. 1» på slutten av 1960-tallet, populariserte sentraliteten til algoritmer innen informatikk. I sin definisjon av algoritmer, var Knuth i samsvar med de matematiske funksjonsbaserte grunnlagene for beregningsteorien. «Det er mange andre i hovedsak likeverdige måter å formulere konseptet med en effektiv beregningsmetode (for eksempel ved bruk av TM-er).»
Knuth spesifiserte eksplisitt at algoritmer er lukket; ingen nye innganger aksepteres når beregningen har begynt: «En algoritme har null eller flere innganger, dvs. størrelser som blir gitt til den først før algoritmen begynner.» Han skilte algoritmer fra vilkårlig beregning som kan involvere I / O. Et eksempel han ga om et problem som ikke er algoritmisk, er følgende instruksjon fra en oppskrift: «kast lett til blandingen er smuldret.» Dette problemet er ikke algoritmisk fordi det er umulig for en datamaskin å vite hvor lenge den skal blandes; dette kan avhenge av en ytre dynamisk skiftende forhold som fuktighet, som ikke kan forutsies med sikkerhet på forhånd.
Selv om det ikke er enighet om den nøyaktige forestillingen om algoritmer, forblir Knuths diskusjon om algoritmer definitiv.
Det første programmeringsspråket på høyt nivå som ble utviklet eksplisitt for å spesifisere algoritmer, var ALGOL (ALGOrithmic Language). Introdusert på slutten av 50-tallet og raffinert gjennom 1960-tallet, fungerte det som en standard for publisering av algoritmer. I samsvar med den funksjonsbaserte konseptualiseringen av algoritmer ga ALGOL ingen konstruksjoner for inndata og utdata, med tanke på disse operasjonene utenfor algoritmene. (Ikke overraskende hindret dette fraværet at industrien vedtok ALGOL for kommersielle applikasjoner.)
På 1960-tallet ble det spredt en rekke programmer for informatikk (CS). I følge Association for Computing Machinery (ACM) økte antall CS-programmer i USA fra 11 i 1964 til 92 i 1968. Denne økningen ble ledsaget av intens aktivitet for å etablere legitimiteten til denne nye disiplinen i akademikernes øyne. samfunnet. ACM spilte en sentral rolle i denne aktiviteten. I 1965 forkynte den rettferdiggjørelsen og beskrivelsen av CS som en disiplin, som tjente som grunnlag for sine anbefalinger fra 1968 for lavere CS-programmer
ACMs beskrivelse av CS identifiserte effektiv transformasjon av informasjon som et sentralt anliggende: “ Datavitenskap er opptatt av informasjon på omtrent samme måte som fysikk er opptatt av energi … Datavitenskapsmannen er interessert i å oppdage de pragmatiske virkemåtene som informasjon kan transformeres til. ” Denne beskrivelsen setter algoritmer i sentrum for informatikk, siden de er «oppskriftene» for å utføre disse effektive transformasjonene av innganger til utganger. Faktisk gjorde ACM dette fokuset på algoritmer eksplisitt i neste setning i rapporten:
«Denne interessen fører til etterforskning om effektive måter å representere informasjon på, effektive algoritmer for å transformere informasjon, effektive språk å uttrykke algoritmer … og effektive måter å oppnå disse til fornuftig pris. ”
Å ha en sentral algoritmisk bekymring, analog med bekymringen med energi i fysikk, bidro til å etablere CS som en legitim akademisk disiplin på nivå med fysikk. Algoritmer har vært sentrale i informatikk den dag i dag.
Sameksistensen av den uformelle (algoritmebaserte) og den formelle (TM-baserte) tilnærmingen for å definere løselige problemer vedvarer til i dag og kan bli funnet i alle moderne lærebøker om algoritmer eller beregningsevne. Dette har vist seg å være veldig praktisk for informatikere, ved å la oss beskrive algoritmisk beregning uformelt ved hjelp av «pseudokode», med kunnskap om at en tilsvarende Turing Machine kan konstrueres.
– Et problem er løst hvis det kan være spesifisert av en algoritme. – Et problem er løst hvis det finnes en Turing-maskin for det.
1960-tallets beslutning av teoretikere og lærere om å plassere algoritmer i sentrum av CS ble tydelig gjenspeilet i tidlige lavere bøker. Imidlertid var det ingen eksplisitt standarddefinisjon av en algoritme, og forskjellige lærebøker valgte å definere dette begrepet annerledes. Mens noen lærebøker som den av Knuth var nøye med å eksplisitt begrense algoritmer til de som beregner funksjoner og derfor tilsvarer Turing Machines, la de fleste teoribøker denne begrensningen underforstått, men ikke uttalt.
Et tidlig eksempel er et lærebok av Hopcroft og Ullman fra 1969, hvis senere utgaver brukes den dag i dag: “En prosedyre er en endelig sekvens av instruksjoner som kan utføres mekanisk, for eksempel et dataprogram …En prosedyre som alltid avsluttes kalles en algoritme. ”
Denne beskrivelsen av algoritmer utelukker ikke eksplisitt ikke-funksjonell beregning som å tilberede mat. Eksemplene deres på forskjellige problemer gjør det imidlertid klart at de bare vurderte funksjonsbasert beregning. Faktisk brukte de ALGOL som eksempler, som ikke engang ga noen konstruksjoner for input og output.
Siden slutten av 60-tallet var ikke programmeringsspråkene på høyt nivå som ble brukt i praksis og undervist i CS-programmer lenger bundet av de algoritmiske begrensningene i tidlig ALGOL. Du kan skrive programmer som interagerte med miljøet deres kontinuerlig gjennom hele beregningen, for eksempel operativsystemer, grafiske brukergrensesnitt eller automatiske kjøretøyer og andre roboter.
Som svar, moderne programmerings lærebøker som ris og Rice (1969) utvidet begrepet algoritmer eksplisitt til å omfatte ikke-funksjonelle problemer. Denne tilnærmingen, som gjenspeiler sentraliteten til algoritmer uten å begrense dem til beregning av funksjoner, ble typisk for ikke-teoriske lærebøker. Temaet for disse lærebøkene er programmeringsmetodikk snarere enn teorien for beregning, og de matematiske prinsippene som ligger til grunn for beregningsmodellene våre ble kastet til side for praktiske skyld.
På overflaten, definisjonen av en algoritme. i Rice and Rice og andre slike lærebøker er ikke forskjellig fra Hopcroft og Ullman: “En algoritme er en oppskrift, et sett med instruksjoner eller spesifikasjonene for en prosess for å gjøre noe. At noe vanligvis løser et eller annet problem. ” Imidlertid er deres eksempler på beregningsbare problemer ikke lenger funksjonsbaserte, og innrømmer bare den slags beregning som Knuth hadde avvist. To slike eksempler, som angivelig kan løses av en algoritme, er å lage potetvodka og fylle en grøft med sand; Knuth ville ha avvist dem begge.
Disse lærebøkene fremsatte ingen krav om TM-ekvivalens for deres «algoritmer». Studentene ble imidlertid ikke gjort oppmerksomme på at denne forestillingen om algoritmer er forskjellig fra Knuths, og at settet med problemer som ble regnet som beregningsdyktig, derved var utvidet. Ved å parre en bredere, mer praktisk, konseptualisering av algoritmer (og dermed beregningsbare problemer) med teorier som hevder at svært beregningsbare problemer kan beregnes av TM-er, ga den algoritmefokuserte CS-læreplanen studentene det feilaktige inntrykket at dette bredere sett med problemer kan også løses av TM-er.
Mens de praktiske informatikerne for lengst har fulgt ledelsen til Rice and Rice og utvidet begrepet algoritmer utover beregning av funksjoner, har teoretisk informatikk beholdt det matematiske verdensbildet som rammer beregning som funksjonsbasert, og avgrenser vår forestilling om et beregningsproblem tilsvarende. Dette gjelder i det minste på lavere nivå. Resultatet er en dikotomi, der datavitenskapssamfunnet tenker på algoritmer som synonymt med den generelle forestillingen om beregning («hva datamaskiner gjør»), men samtidig som å være ekvivalent med Turing Machines.
Jeg trodde Jeg måtte skrive dette lange svaret for å gjøre folk oppmerksomme på denne dikotomien. Som jeg sa i begynnelsen, er forestillingen om en algoritme uformell. Vi kan tenke på det som ekvivalent med beregning av funksjoner (eller Turing Machines), eller vi kan tenke på det som noe du kan skrive et program for, inkludert sanntids interaktive programmer som operativsystemer eller automatiske biler. Men de to definisjonene er ikke likeverdige, til tross for den vanlige forvirringen mot det motsatte.