Bedste svar
Der er ikke noget svar på dette.
Lad os finde svar på denne problemstilling:
Q. Hvordan finder jeg ud af, at en algoritme klarer sig bedre?
A. Mest almindelige måder at sammenligne algoritmer på:
1) Tidskompleksitet
2) Rumkompleksitet
3) Løsningskvalitet (muligvis ikke være anvendelig, hvis det foreslås at løse et problem nøjagtigt). Denne kan være en kæmpe faktor, hvis vi taler om tilnærmelsesalgoritmer.
4) Let implementering / tilpasning af algoritme. Nogle algoritmer kan have en masse overhead til at implementere korrekt. Der er undertiden mere passende algoritmer til din applikation. F.eks. vil parallelle computere de fleste finde Bellman-Ford mere nyttigt end Dijkstras algoritme på grund af den måde, Bellman-Ford fungerer på.
Men tid og kompleksitet er ikke * altid * den ønskelige funktion at maksimere; Jeg vil give to eksempler.
Den ene er “numerisk stabilitet” , et træk ved algoritmer i både lineær algebra og i differentialligninger. Vi bruger både mere algoritmisk tid og mere algoritmisk kompleksitet på algoritmer, der er mere numerisk stabile. I lineær algebra forårsages ustabilitet generelt, når en algoritme støder på tal for tæt på nul eller uendeligt eller begge dele på grund af den endelige repræsentation af tal kan opløsning gå tabt. Generelt forårsager dette meget lidt forskellige tal, bare et par epsiloner, der adskiller sig fra hinanden (hvor epsilon er det mindste tal, der kan føjes til en på en maskine og får et resultat! = 1), for at producere store forskelle i svaret. Så for eksempel bruger vi meget tid og pladskompleksitet ved at “dreje” i LU-faktoriseringen for at få en stabil algoritme; uden at dreje er LU ikke stabil. Ligeledes har vi algoritmer, der ikke gør andet end “betingelse” -matricer for at undgå ustabilitet.
Et andet eksempel er “robusthed” i dens tekniske statistiske betydning. Robusthed betyder et mål eller en algoritme, der * ikke * er følsom over for outliers. Så for eksempel, når jeg tilpasser en mindste kvadratlinie til et sæt punkter, kan linjen være stærkt skæv med en enkelt ekstrem stor værdi. Selvom jeg har 99 par tal, der danner en perfekt 45 graders linje, hvis jeg tilføjer et enkelt outlier-par, for hvilket Y-værdien er hundrede gange, hvad det “skulle” være at falde på den samme linje, vil den monterede linje være alvorligt skæv fra 45 graders linie. Algoritmen vil “opgive” den perfekte pasform til 99 point for bedre at repræsentere det ene outlier-punkt. Det er * ikke * robust.
En robust tilgang til mindste kvadrater er i stedet for at finde den linje, der minimerer summen af kvadrerede fejl, der oprettes ved at bruge den linje, at finde den linje, der minimerer * medianen * af de kvadrerede fejl oprettet ved hjælp af denne linje. I eksemplet er denne linje 45 graders linje, og medianen af de kvadrerede fejl er nul, og outlier-punktet (og faktisk op til 98 mere skøre outliers) ville blive ignoreret fuldstændigt. Linjen på 45 grader ville blive fundet.
Der findes lignende robuste algoritmer til tilpasning af statistiske kurver, findelse af figurer osv. De er dog dyre i tid, nogle gange alvorligt. Men tidsomkostningerne er det værd, fordi robuste statistikker effektivt er immune over for “støj” i signaler, hvor mindst kvadratiske fejltilgange ikke er. Den virkelige verden er fuld af både støj og afvigelser, nogle af dem forårsaget af menneskelige eller maskinfejl, især i pixelerede billeder eller samplet lyd. Under sådanne omstændigheder kan en mere tidskrævende robust algoritme finde signaler i et støjende miljø, hvor hurtigere algoritmer producerer svar, der er så beskadiget af støj, at de er ubrugelige eller endda farlige, hvis de accepteres.
I nogle tilfælde er tid og rumkompleksitet er ikke nær så vigtig som at finde et svar, der mest sandsynligt vil modellere det faktiske signal på trods af støj og forringelse af signalet.
Svar
Algoritmer stammer fra matematik som “opskrifter” til udførelse af funktionsbaseret beregning, der kan følges mekanisk. I det funktionsbaserede matematiske verdensbillede skal alle input specificeres i starten af beregningen, som fortsætter lukket. Begrebet en algoritme er i sagens natur uformelt, da en algoritmisk beskrivelse ikke er begrænset til et enkelt sprog eller formalisme.
Det ældste eksempel er måske Euclids algoritme til at finde fælles skillevægge. Algoritmer fanger, hvad det betyder for en beregning at være “effektiv”. Ligesom matematiske formler fortæller algoritmer os, hvordan vi beregner en værdi; i modsætning til dem kan algoritmer involvere det, vi nu kalder sløjfer eller grene.
Algoritmens rolle: I betragtning af en vis begrænset inputværdi x beskriver en algoritme trinene til effektiv omdannelse til en outputværdi y, hvor y er f (x) for en eller anden rekursiv funktion f.
Algoritmer blev vedtaget af de tidlige dataloger i 1950erne, der lavede forbindelsen mellem algoritmer og Turing Machines (TMer, en formel beregningsmodel fra 1936), der svarede til deres ekspressivitet.
Knuths berømte og indflydelsesrige lærebog “The Art of Computer Programming, Vol. 1” i slutningen af 1960erne populariserede centraliteten af algoritmer inden for datalogi. I sin definition af algoritmer var Knuth i overensstemmelse med de matematiske funktionsbaserede fundamenter for beregningsteorien. ”Der er mange andre i det væsentlige ækvivalente måder at formulere begrebet en effektiv beregningsmetode (for eksempel ved hjælp af TMer).”
Knuth specificerede eksplicit, at algoritmer er lukkede; ingen nye input accepteres, når beregningen er begyndt: “En algoritme har nul eller flere input, dvs. størrelser, der oprindeligt gives til den, før algoritmen begynder.” Han adskilte algoritmer fra vilkårlig beregning, der kan involvere I / O. Et eksempel, han gav om et problem, der ikke er algoritmisk, er følgende instruktion fra en opskrift: “kast let, indtil blandingen er smuldret.” Dette problem er ikke algoritmisk, fordi det er umuligt for en computer at vide, hvor længe den skal blandes; dette kan afhænge af eksterne, dynamisk skiftende forhold såsom fugtighed, der ikke kan forudsiges med sikkerhed på forhånd.
Selvom der ikke er enighed om den nøjagtige opfattelse af algoritmer, forbliver Knuths diskussion af algoritmer definitiv.
Det første programmeringssprog på højt niveau, der blev udviklet udtrykkeligt til at specificere algoritmer, var ALGOL (ALGOrithmic Language). Introduceret i slutningen af 50erne og raffineret gennem 1960erne, fungerede det som en standard for offentliggørelse af algoritmer. I overensstemmelse med den funktionsbaserede konceptualisering af algoritmer leverede ALGOL ingen konstruktioner til input og output, i betragtning af disse operationer uden for algoritmer. (Ikke overraskende forhindrede dette fravær industriens vedtagelse af ALGOL til kommercielle applikationer.)
1960erne oplevede en spredning af bachelor-programmer inden for datalogi (CS). Ifølge Association for Computing Machinery (ACM) steg antallet af CS-programmer i USA fra 11 i 1964 til 92 i 1968. Denne stigning blev ledsaget af intens aktivitet for at etablere legitimiteten af denne nye disciplin i akademiens øjne fællesskab. ACM spillede en central rolle i denne aktivitet. I 1965 erklærede det retfærdiggørelsen og beskrivelsen af CS som en disciplin, der tjente som grundlag for dens henstillinger fra 1968 til bachelor-CS-programmer
ACMs beskrivelse af CS identificerede effektiv transformation af information som et centralt anliggende: “ Datalogi beskæftiger sig med information i næsten samme forstand som fysik beskæftiger sig med energi … Computerforskeren er interesseret i at opdage de pragmatiske måder, hvormed information kan transformeres. ” Denne beskrivelse placerer algoritmer i centrum for datalogi, da de er “opskrifterne” til at udføre disse effektive transformationer af input til output. Faktisk gjorde ACM dette fokus på algoritmer eksplicit i næste sætning i deres rapport:
“Denne interesse fører til undersøgelse af effektive måder at repræsentere information på, effektive algoritmer til at transformere information, effektive sprog, som de kan udtrykke algoritmer … og effektive måder at opnå disse til en rimelig pris. ”
At have en central algoritmisk bekymring, analog med bekymringen med energi i fysik, hjalp med at etablere CS som en legitim akademisk disciplin på niveau med fysik. Algoritmer er forblevet centrale inden for datalogi den dag i dag.
Sameksistensen af den uformelle (algoritmebaserede) og den formelle (TM-baserede) tilgang til at definere løselige problemer fortsætter den dag i dag og kan findes i alle moderne lærebøger om algoritmer eller beregningsevne. Dette har vist sig meget praktisk for computerforskere ved at lade os beskrive algoritmisk beregning uformelt ved hjælp af “pseudocode” med den viden, at en ækvivalent Turing Machine kan konstrueres.
– Et problem kan løses, hvis det kan være specificeret af en algoritme. – Et problem kan løses, hvis der findes en Turing-maskine til den.
1960ernes beslutning af teoretikere og undervisere om at placere algoritmer i centrum af CS blev tydeligt afspejlet i tidlige undervisningsbøger. Der var dog ingen eksplicit standarddefinition af en algoritme, og forskellige lærebøger valgte at definere dette udtryk forskelligt. Mens nogle lærebøger som den af Knuth var omhyggelige med eksplicit at begrænse algoritmer til dem, der beregner funktioner og derfor svarer til Turing Machines, efterlod de fleste teoribøger denne begrænsning underforstået, men ikke angivet.
Et tidligt eksempel er et lærebog af Hopcroft og Ullman fra 1969, hvis senere udgaver bruges den dag i dag: ”En procedure er en endelig række af instruktioner, der kan udføres mekanisk, såsom et computerprogram …En procedure, der altid afsluttes, kaldes en algoritme. ”
Denne beskrivelse af en algoritme udelukker ikke eksplicit ikke-funktionel beregning såsom madlavning. Imidlertid gør deres eksempler på forskellige problemer det klart, at de kun overvejede funktionsbaseret beregning. Faktisk brugte de ALGOL til deres eksempler, som ikke engang tilbød nogen konstruktioner til input og output.
Siden slutningen af 60erne var de programmeringssprog på højt niveau, der blev brugt i praksis og undervist i CS-programmer, ikke længere bundet af de algoritmiske begrænsninger af tidlig ALGOL. Du kunne skrive programmer, der interagerede med deres miljø på en løbende måde i hele beregningen, såsom operativsystemer, grafiske brugergrænseflader eller automatiske køretøjer og andre robotter.
Som svar, nutidige programmerings lærebøger som ris og Rice (1969) udvidede udtrykkeligt begrebet algoritmer til at omfatte ikke-funktionelle problemer. Denne tilgang, der afspejler algoritmernes centralitet uden at begrænse dem til beregning af funktioner, blev typisk for ikke-teoriske lærebøger. Emnet for disse lærebøger er programmeringsmetodologi snarere end teorien om beregning, og de matematiske principper, der ligger til grund for vores modeller for beregning, blev kastet til side for at gøre det praktisk.
På overfladen er definitionen af en algoritme i Rice and Rice og andre sådanne lærebøger adskiller sig ikke fra Hopcroft og Ullman: ”En algoritme er en opskrift, et sæt instruktioner eller specifikationerne for en proces til at gøre noget. At noget normalt løser et eller andet problem. ” Imidlertid er deres eksempler på beregbare problemer ikke længere funktionsbaseret og indrømmer kun den slags beregning, som Knuth havde afvist. To sådanne eksempler, der angiveligt kan løses ved hjælp af en algoritme, fremstiller kartoffelvodka og fylder en grøft med sand; Knuth ville have afvist dem begge.
Disse lærebøger fremsatte ingen krav om TM-ækvivalens for deres “algoritmer”. De studerende blev imidlertid ikke opmærksomme på, at denne opfattelse af algoritmer er forskellig fra Knuths, og at det sæt problemer, der betragtes som beregningsfuldt, derved var blevet udvidet. Ved at parre en bredere, mere praktisk konceptualisering af algoritmer (og dermed beregningsbare problemer) med teorier, der hævder, at meget beregningsværdigt problem kan beregnes af TMer, efterlod den algoritmefokuserede CS-læseplan studerende med det fejlagtige indtryk, at dette bredere sæt af problemer kunne også løses af TMer.
Mens de praktiske computerforskere for længe siden har fulgt Rice and Rices ledelse og udvidet begrebet algoritmer ud over beregningen af funktioner, har teoretisk datalogi bevaret den matematiske verdensbillede, der rammer beregning som funktionsbaseret og afgrænser vores forestilling om et beregningsproblem i overensstemmelse hermed. Dette gælder i det mindste på lavere niveau. Resultatet er en dikotomi, hvor datalogisk samfund tænker på algoritmer som synonyme med den generelle opfattelse af beregning (“hvad computere gør”), men samtidig på samme tid som at være ækvivalente med Turing Machines.
Jeg troede Jeg var nødt til at skrive dette lange svar for at gøre folk opmærksomme på denne dikotomi. Som jeg sagde i begyndelsen, er begrebet en algoritme uformel. Vi kan tænke på det som svarende til beregning af funktioner (eller til Turing Machines), eller vi kan tænke på det som noget, du kan skrive et program til, herunder interaktive realtidsprogrammer som operativsystemer eller automatiske biler. Men de to definitioner er ikke ækvivalente, på trods af den fælles forvirring mod det modsatte.