Vraag Wat is een eenvoudige Engelse uitleg van de "Big O" -notatie?


Ik zou de voorkeur geven aan zo min mogelijk formele definitie en eenvoudige wiskunde.


4529
2018-01-28 11:10


oorsprong


antwoorden:


Snelle opmerking, dit is bijna zeker verwarrend Big O-notatie (wat een bovengrens is) met Theta-notatie (die een tweezijdige binding is). Naar mijn ervaring is dit eigenlijk typerend voor discussies in niet-academische omgevingen. Excuses voor eventuele verwarring veroorzaakt.


Big O-complexiteit kan met deze grafiek worden gevisualiseerd:

Big O Analysis

De eenvoudigste definitie die ik kan geven voor Big-O-notatie is deze:

Big-O-notatie is een relatieve weergave van de complexiteit van een algoritme.

Er zijn enkele belangrijke en bewust gekozen woorden in die zin:

  • familielid: je kunt appels alleen met appels vergelijken. U kunt een algoritme niet vergelijken om rekenkundige vermenigvuldiging te doen met een algoritme dat een lijst van gehele getallen sorteert. Maar een vergelijking van twee algoritmen om rekenkundige bewerkingen te doen (één vermenigvuldiging, één optelling) zal u iets zinnigs vertellen;
  • vertegenwoordiging: Big-O (in zijn eenvoudigste vorm) vermindert de vergelijking tussen algoritmen tot een enkele variabele. Die variabele wordt gekozen op basis van waarnemingen of aannames. Sorteeralgoritmen worden bijvoorbeeld meestal vergeleken op basis van vergelijkingsbewerkingen (twee knooppunten vergelijken om hun relatieve volgorde te bepalen). Dit veronderstelt dat vergelijking duur is. Maar wat als vergelijking goedkoop is, maar ruilen duur is? Het verandert de vergelijking; en
  • complexiteit: als het me een seconde kost om 10.000 elementen te sorteren, hoe lang zal het duren om een ​​miljoen te sorteren? Complexiteit is in dit geval een relatieve maatstaf voor iets anders.

Kom terug en herlees het bovenstaande als je de rest hebt gelezen.

Het beste voorbeeld van Big-O dat ik kan bedenken is rekenen. Neem twee nummers (123456 en 789012). De elementaire rekenkundige bewerkingen die we op school leerden waren:

  • Bovendien;
  • aftrekken;
  • vermenigvuldiging; en
  • afdeling.

Elk van deze is een operatie of een probleem. Een methode om deze op te lossen wordt een algoritme.

Optellen is de eenvoudigste. U lijnt de getallen naar boven (naar rechts) en voegt de cijfers toe in een kolom die het laatste nummer van die optelling in het resultaat schrijft. Het 'tienen'-deel van dat getal wordt overgedragen naar de volgende kolom.

Laten we aannemen dat de toevoeging van deze nummers de duurste bewerking in dit algoritme is. Het spreekt vanzelf dat om deze twee getallen bij elkaar te voegen we 6 cijfers moeten optellen (en mogelijk een 7e moeten dragen). Als we twee 100-cijferige cijfers bij elkaar optellen, moeten we 100 toevoegingen doen. Als we toevoegen twee 10.000-cijferige nummers moeten we 10.000 toevoegingen doen.

Zie het patroon? De ingewikkeldheid (zijnde het aantal bewerkingen) is recht evenredig met het aantal cijfers n in het grotere aantal. We noemen dit Op) of lineaire complexiteit.

Aftrekken is vergelijkbaar (behalve dat je misschien moet lenen in plaats van dragen).

Vermenigvuldiging is anders. Je lijnt de getallen op, neemt het eerste cijfer in het onderste getal en vermenigvuldigt het beurtelings met elk cijfer in het bovenste getal enzovoort door elk cijfer. Dus om onze twee 6-cijferige getallen te vermenigvuldigen, moeten we 36 vermenigvuldigingen doen. We moeten misschien wel 10 of 11 kolomvullingen doen om ook het eindresultaat te krijgen.

Als we twee 100-cijferige getallen hebben, moeten we 10.000 vermenigvuldigingen en 200 optellingen doen. Voor twee miljoencijferige getallen moeten we één biljoen doen (1012) vermenigvuldigingen en twee miljoen toevoegingen.

Aangezien het algoritme schaalt met n-kwadraat, dit is Op2) of kwadratische complexiteit. Dit is een goed moment om een ​​ander belangrijk concept te introduceren:

We geven alleen om het grootste deel van de complexiteit.

De scherpzinnige heeft zich misschien gerealiseerd dat we het aantal bewerkingen kunnen weergeven als: n2 + 2n. Maar zoals u in ons voorbeeld met twee cijfers van een miljoen cijfers per stuk hebt gezien, wordt de tweede term (2n) onbeduidend (goed voor 0,0002% van de totale bewerkingen in die fase).

Het valt ons op dat we hier het slechtste scenario hebben aangenomen. Tijdens het vermenigvuldigen van 6-cijferige cijfers als een van hen 4 cijfers is en de andere 6 cijfers, dan hebben we slechts 24 vermenigvuldigingen. Toch berekenen we het slechtste scenario voor die 'n', d.w.z. wanneer beide 6-cijferige nummers zijn. Vandaar dat Big-O-notatie gaat over het Worst-case scenario van een algoritme

Het telefoonboek

Het volgende beste voorbeeld dat ik kan bedenken is het telefoonboek, gewoonlijk de Witte Gids of iets dergelijks genoemd, maar het zal van land tot land verschillen. Maar ik heb het over degene die mensen op achternaam vermeldt en dan initialen of voornaam, eventueel adres en dan telefoonnummers.

Als u nu een computer zou instrueren om het telefoonnummer voor 'John Smith' op te zoeken in een telefoonboek met 1.000.000 namen, wat zou u dan doen? Negerend het feit dat je kon raden hoe ver in de S's begonnen is (laten we aannemen dat je dat niet kunt), wat zou je doen?

Een typische implementatie zou kunnen zijn om zich naar het midden open te stellen, de 500.000 te nementh en vergelijk het met "Smith". Als het toevallig "Smith, John" is, hebben we echt geluk gehad. Veel waarschijnlijker is dat "John Smith" vóór of na die naam zal zijn. Als dat het geval is, splitsen we de laatste helft van het telefoonboek in twee en herhalen. Als dat eerder is, delen we de eerste helft van het telefoonboek door en herhalen. Enzovoort.

Dit wordt a genoemd Binaire zoekopdracht en wordt elke dag in de programmering gebruikt, of je het nu beseft of niet.

Dus als je een naam in een telefoonboek van een miljoen namen wilt vinden, kun je elke naam daadwerkelijk vinden door dit maximaal 20 keer te doen. Bij het vergelijken van zoekalgoritmen besluiten we dat deze vergelijking onze 'n' is.

  • Voor een telefoonboek van 3 namen zijn er maximaal 2 vergelijkingen nodig.
  • Voor 7 duurt het maximaal 3.
  • Voor 15 duurt het 4.
  • ...
  • Voor 1.000.000 zijn er 20 nodig.

Dat is ontzettend goed, niet waar?

In Big-O-termen is dit O (log n) of logaritmische complexiteit. Nu kan de logaritme in kwestie ln zijn (basis e), log10, log2 of een andere basis. Het maakt niet uit dat het nog steeds O (log n) is net als O (2n2) en O (100n2) zijn nog steeds beide O (n2).

Het is op dit moment de moeite waard om uit te leggen dat Big O kan worden gebruikt om drie cases met een algoritme te bepalen:

  • Beste case: In het zoeken naar telefoonboeken is het beste geval dat we de naam in één vergelijking vinden. Dit is O (1) of constante complexiteit;
  • Verwachte case: Zoals hierboven besproken is dit O (log n); en
  • Het slechtste geval: Dit is ook O (log n).

Normaal geven we niet om de beste zaak. We zijn geïnteresseerd in de verwachte en slechtste zaak. Soms zal de ene of de andere belangrijker zijn.

Terug naar het telefoonboek.

Wat als u een telefoonnummer hebt en een naam wilt weten? De politie heeft een telefoonboek in omgekeerde volgorde, maar dergelijke opzoekingen worden geweigerd aan het grote publiek. Of zijn ze? Technisch gezien kun je een nummer omkeren in een gewoon telefoonboek. Hoe?

Je begint bij de voornaam en vergelijkt het nummer. Als het een match is, geweldig, zo niet, ga je naar de volgende. Je moet het op deze manier doen omdat het telefoonboek dat is ongeordende (op elk telefoonnummer).

Dus om een ​​naam te vinden op basis van het telefoonnummer (reverse lookup):

  • Beste case: O (1);
  • Verwachte case: O (n) (voor 500.000); en
  • Het slechtste geval: O (n) (voor 1.000.000).

De reizende verkoper

Dit is een beroemd probleem in de informatica en verdient een vermelding. In dit probleem heb je N steden. Elk van die steden is verbonden met 1 of meer andere steden via een weg van een bepaalde afstand. Het probleem van de reizende verkoper is om de kortste rondleiding te vinden die elke stad bezoekt.

Klinkt eenvoudig? Denk nog eens na.

Als je 3 steden A, B en C hebt met wegen tussen alle paren, kun je gaan:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Eigenlijk is er minder dan dat, omdat sommige van deze equivalent zijn (A → B → C en C → B → A zijn gelijkwaardig, bijvoorbeeld omdat ze dezelfde wegen gebruiken, alleen in omgekeerde volgorde).

In werkelijkheid zijn er 3 mogelijkheden.

  • Breng dit naar 4 steden en je hebt (iirc) 12 mogelijkheden.
  • Met 5 is het 60.
  • 6 wordt 360.

Dit is een functie van een wiskundige bewerking genaamd a factorial. Eigenlijk:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • ...
  • 25! = 25 x 24 x ... x 2 x 1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50! = 50 × 49 × ... × 2 × 1 = 3.04140932 × 1064

Dus de Big-O van het probleem van de reizende verkoper is Op!) of factoriële of combinatorische complexiteit.

Tegen de tijd dat je 200 steden bereikt, is er niet genoeg tijd over in het universum om het probleem met traditionele computers op te lossen.

Iets om over na te denken.

Polynomische tijd

Een ander punt dat ik snel wilde noemen, is dat elk algoritme met een complexiteit van Opeen) zou hebben veelterm complexiteit of is oplosbaar in polynomische tijd.

O (n), O (n2) enz. zijn allemaal polynomiale tijd. Sommige problemen kunnen niet worden opgelost in polynomiale tijd. Bepaalde dingen worden hierdoor in de wereld gebruikt. Public Key Cryptography is een goed voorbeeld. Het is rekenkundig moeilijk om twee priemgetallen van een zeer groot aantal te vinden. Als dat niet het geval was, konden we de openbare-sleutelsystemen die we gebruiken niet gebruiken.

Hoe dan ook, dat is het voor mijn (hopelijk duidelijke Engelse) uitleg van Big O (herzien).


6089
2018-01-28 11:18



Het laat zien hoe een algoritme schaalt.

Op2): bekend als Kwadratische complexiteit

  • 1 item: 1 seconde
  • 10 items: 100 seconden
  • 100 items: 10000 seconden

Merk op dat het aantal items met een factor 10 toeneemt, maar dat de tijd met een factor 10 toeneemt2. In principe is n = 10 en dus O (n2) geeft ons de schaalfactor n2 welke is 102.

Op): bekend als Lineaire complexiteit

  • 1 item: 1 seconde
  • 10 items: 10 seconden
  • 100 items: 100 seconden

Deze keer neemt het aantal items toe met een factor 10, en dat geldt ook voor de tijd. n = 10 en de schaalfactor van O (n) is 10.

O (1): bekend als Constante complexiteit

  • 1 item: 1 seconde
  • 10 items: 1 seconde
  • 100 items: 1 seconde

Het aantal items neemt nog steeds met een factor 10 toe, maar de schaalfactor van O (1) is altijd 1.

O (log n): bekend als Logaritmische complexiteit

  • 1 item: 1 seconde
  • 10 items: 2 seconden
  • 100 items: 3 seconden
  • 1000 items: 4 seconden
  • 10000 items: 5 seconden

Het aantal berekeningen wordt alleen verhoogd met een log van de invoerwaarde. Dus in dit geval, ervan uitgaande dat elke berekening 1 seconde duurt, is het log van de invoer n is de tijd die nodig is, vandaar log n.

Dat is de kern ervan. Ze verminderen de wiskunde zodat het misschien niet precies n is2 of wat ze ook zeggen dat het is, maar dat is de dominante factor in de schaal.


662
2018-01-28 11:28



Big-O notatie (ook wel "asymptotische groei" -notatie genoemd) welke functies "eruitzien" wanneer je constante factoren en dingen in de buurt van de oorsprong negeert. We gebruiken het om over te praten hoe ding schaal.


Basics

voor "voldoende" grote ingangen ...

  • f(x) ∈ O(upperbound) middelen f "groeit niet sneller dan" upperbound
  • f(x) ∈ Ɵ(justlikethis) gemiddelde f "groeit precies zoals" justlikethis
  • f(x) ∈ Ω(lowerbound) middelen f "groeit niet langzamer dan" lowerbound

big-O notatie geeft niet om constante factoren: de functie 9x² wordt gezegd "groeien precies zoals" 10x². Noch doet groot-O asymptotische notatie geeft om niet-asymptotische dingen ("dingen in de buurt van de oorsprong" of "wat gebeurt er als de probleemomvang klein is"): de functie 10x² wordt gezegd "groeien precies zoals" 10x² - x + 2.

Waarom zou je de kleinere delen van de vergelijking willen negeren? Omdat ze volledig in de schaduw raken van de grote delen van de vergelijking als je naar grotere en grotere schalen kijkt; hun bijdrage wordt kleiner en irrelevant. (Zie voorbeeld sectie.)

Anders gezegd, het gaat allemaal om het verhouding als je naar het oneindige gaat. Als u de werkelijke tijd verdeelt die nodig is voor de O(...), u krijgt een constante factor in de limiet van grote ingangen. Intuïtief is dit logisch: functies "schalen als" elkaar als je de ene kunt vermenigvuldigen om de andere te krijgen. Dat wil zeggen, wanneer we zeggen ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... Dit betekent dat voor "groot genoeg" probleemmaten N (als we dingen naast de oorsprong negeren), bestaat er een constante (bijvoorbeeld 2,5, volledig verzonnen), zodanig dat:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Er zijn veel keuzes van constant; vaak staat de "beste" keuze bekend als de "constante factor" van het algoritme ... maar we negeren het vaak alsof we niet-grootste termen negeren (zie de sectie over constante factoren voor waarom ze er meestal niet toe doen). Je kunt de bovenstaande vergelijking ook beschouwen als een band en zeggen:In het slechtste geval zal de benodigde tijd nooit slechter zijn dan ongeveer N*log(N), binnen een factor 2,5 (een constante factor waar we niet veel om geven)".

In het algemeen, O(...) is de meest bruikbare omdat we vaak geven om het worst-case gedrag. Als f(x) staat voor iets "slecht", zoals processor- of geheugengebruik, dan "f(x) ∈ O(upperbound)" middelen "upperbound is het slechtste scenario van processor / geheugengebruik ".


toepassingen

Als puur wiskundig construct is de grote O-notatie niet beperkt tot het praten over verwerkingstijd en geheugen. Je kunt het gebruiken om de asymptotiek te bespreken van alles waar schaalvergroting zinvol is, zoals:

  • het aantal mogelijke handdrukken onder N mensen op een feestje (Ɵ(N²), specifiek N(N-1)/2, maar waar het om gaat is dat het "schaalt als" )
  • waarschijnlijkheidsverwachting van het aantal mensen dat enige virale marketing gezien heeft als een functie van de tijd
  • hoe de latentie van de website zich verhoudt tot het aantal verwerkingseenheden in een CPU of GPU of een computercluster
  • hoe warmteafgifteschalen op de CPU afsterft als een functie van transistortelling, spanning, etc.
  • hoeveel tijd een algoritme nodig heeft om te werken, als een functie van de invoergrootte
  • hoeveel ruimte een algoritme nodig heeft om te werken, als een functie van de invoergrootte

Voorbeeld

Voor het voorbeeld van de handdruk schudt iedereen in een kamer de hand van iedereen. In dat voorbeeld #handshakes ∈ Ɵ(N²). Waarom?

Maak een back-up: het aantal handdrukken is precies n-kies-2 of N*(N-1)/2 (elk van de N-mensen schudt de handen van N-1 andere mensen, maar deze dubbeltellingen worden gedeeld door 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Echter, voor zeer grote aantallen mensen, de lineaire term N is overschaduwd en draagt ​​effectief 0 bij aan de verhouding (in de grafiek: de fractie lege vakken op de diagonaal over totale vakken wordt kleiner naarmate het aantal deelnemers groter wordt). Daarom is het schaalgedrag order N²of het aantal handdrukken "groeit als N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

Het is alsof de lege vakken op de diagonaal van de kaart (N * (N-1) / 2 vinkjes) er niet eens waren (N2 vinkjes asymptotisch aan).

(tijdelijke uitweiding van "gewoon Engels" :) Als je dit jezelf wilde bewijzen, zou je een eenvoudige algebra over de ratio kunnen uitvoeren om het in meerdere termen op te splitsen (limbetekent "beschouwd als in de limiet van", negeer het gewoon als je het niet hebt gezien, het is gewoon een notatie voor "en N is echt heel groot"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Het aantal handdrukken lijkt 'zo' op x² voor grote waarden, dat als we de verhouding # handshakes / x² zouden noteren, het feit dat we niet nodig hebben precies x²-handdrukken zouden niet eens in het decimaalteken verschijnen voor een willekeurig grote tijd.

bijv. voor x = 1 miljoen, verhouding # handshakes / x²: 0.499999 ...


Intuïtie bouwen

Hiermee kunnen we uitspraken doen als ...

"Voor groot genoeg inputize = N, ongeacht wat de constante factor is, als ik dubbele de ingangsgrootte


362
2017-07-08 04:46



EDIT: Korte opmerking, dit is bijna zeker verwarrend Big O-notatie (wat een bovengrens is) met Theta-notatie (die zowel een boven- als een ondergrens is). Naar mijn ervaring is dit eigenlijk typerend voor discussies in niet-academische omgevingen. Excuses voor eventuele verwarring veroorzaakt.

In één zin: hoe lang duurt het om het af te ronden als de omvang van je werk stijgt?

Vanzelfsprekend wordt alleen "size" gebruikt als de input en "time takes" als de output - hetzelfde idee is van toepassing als je het wilt hebben over geheugengebruik etc.

Hier is een voorbeeld van N T-shirts die we willen drogen. Goed uitgaan van het is ongelooflijk snel om ze in de droogpositie te krijgen (de menselijke interactie is verwaarloosbaar). Dat is niet het geval in het echte leven, natuurlijk ...

  • Buiten een waslijn gebruiken: ervan uitgaande dat je een oneindig grote achtertuin hebt, droogt het wasgoed in O (1) -tijd. Hoeveel je er ook van hebt, het krijgt dezelfde zon en frisse lucht, dus de maat heeft geen invloed op de droogtijd.

  • Met behulp van een wasdroger: je steekt 10 shirts in elke lading en dan zijn ze een uur later klaar. (Negeer de werkelijke cijfers hier - ze zijn niet relevant.) Dus het drogen van 50 shirts duurt over 5 keer zo lang als het drogen van 10 shirts.

  • Alles in een droogkast stoppen: als we alles op één grote stapel leggen en gewoon de algemene warmte laten doen, duurt het lang voordat de middelste shirts droog zijn. Ik zou niet graag naar de details raden, maar ik vermoed dat dit ten minste O (N ^ 2) is - naarmate u de waslading verhoogt, neemt de droogtijd sneller toe.

Een belangrijk aspect van de "grote O" -notatie is dat het niet zeggen welk algoritme sneller zal zijn voor een gegeven grootte. Neem een ​​hashtabel (tekenreeks, integerwaarde) versus een reeks paren (tekenreeks, geheel getal). Is het sneller om een ​​sleutel te vinden in de hashtabel of een element in de array, gebaseerd op een string? (dat wil zeggen voor de array, "vind het eerste element waar het stringgedeelte overeenkomt met de gegeven sleutel.") Hashtables worden over het algemeen afgeschreven (~ = "gemiddeld") O (1) - als ze eenmaal zijn ingesteld, duurt het ongeveer tegelijkertijd om een ​​item in een 100-itemtabel te vinden zoals in een tabel met 1.000.000 invoeritems. Het vinden van een element in een array (op basis van inhoud in plaats van index) is lineair, d.w.z. O (N) - gemiddeld zul je de helft van de ingaven moeten bekijken.

Maakt dit een hashtable sneller dan een array voor lookups? Niet noodzakelijk. Als je een zeer kleine verzameling items hebt, is een array mogelijk sneller - je kunt mogelijk alle reeksen controleren in de tijd die nodig is om de hashcode van degene die je bekijkt te berekenen. Naarmate de dataset echter groter wordt, zal de hashtable uiteindelijk de array verslaan.


237
2018-01-28 11:16



Big O beschrijft een bovengrens van het groeigedrag van een functie, bijvoorbeeld de looptijd van een programma, wanneer de ingangen groot worden.

Voorbeelden:

  • O (n): als ik de invoerformaat verdubbel, wordt de runtime verdubbeld

  • Op2): Als de invoergrootte de runtime-verviervoudigingen verdubbelt

  • O (log n): als de invoergrootte verdubbelt, verhoogt de looptijd met één

  • O (2n): Als de ingangsgrootte met één toeneemt, verdubbelt de looptijd

De invoergrootte is meestal de ruimte in bits die nodig is om de invoer te vertegenwoordigen.


120
2018-01-28 11:23



Big O-notatie wordt meestal door programmeurs gebruikt als een geschatte maat voor hoe lang een berekening (algoritme) duurt om te worden uitgedrukt als een functie van de grootte van de invoerset.

Big O is handig om te vergelijken hoe goed twee algoritmen zullen opschalen naarmate het aantal ingangen toeneemt.

Preciezer Big O-notatie wordt gebruikt om het asymptotische gedrag van een functie uit te drukken. Dat betekent hoe de functie zich gedraagt ​​als deze het oneindige nadert.

In veel gevallen valt de "O" van een algoritme in een van de volgende gevallen:

  • O (1) - De tijd om te voltooien is hetzelfde, ongeacht de grootte van de ingevoerde reeks. Een voorbeeld is toegang tot een array-element per index.
  • O (Log N) - De tijd om te voltooien neemt ongeveer toe in lijn met log2 (n). Bijvoorbeeld 1024 items duurt ongeveer twee keer zo lang als 32 items, omdat Log2 (1024) = 10 en Log2 (32) = 5. Een voorbeeld is het vinden van een item in een binaire zoekboom (BST).
  • OP) - Tijd om te voltooien, schalen lineair met de grootte van de invoerset. Met andere woorden, als u het aantal items in de invoerset verdubbelt, duurt het algoritme ongeveer twee keer zo lang. Een voorbeeld is het tellen van het aantal items in een gekoppelde lijst.
  • O (N Log N) - De tijd om te voltooien neemt toe met het aantal items maal het resultaat van Log2 (N). Een voorbeeld hiervan is hoop sorteren en Snel sorteren.
  • O (N ^ 2) - De tijd om te voltooien is ongeveer gelijk aan het kwadraat van het aantal items. Een voorbeeld hiervan is bellen soort.
  • OP!) - De tijd om te voltooien is de factorie van de invoerset. Een voorbeeld hiervan is de reizende verkoper probleem brute-force oplossing.

Big O negeert factoren die niet op een zinvolle manier bijdragen aan de groeicurve van een functie naarmate de inputgrootte toeneemt in de richting van oneindig. Dit betekent dat constanten die worden toegevoegd aan of vermenigvuldigd met de functie eenvoudig worden genegeerd.


97
2017-09-05 16:31



Big O is gewoon een manier om jezelf "uit te drukken" op een veel voorkomende manier: "Hoeveel tijd / ruimte kost het om mijn code uit te voeren?".

U kunt vaak O (n), O (n2), O (nlogn) enzovoort, dit zijn allemaal manieren om te laten zien; Hoe verandert een algoritme?

O (n) betekent Big O is n, en nu zou je kunnen denken: "Wat is n !?" Nou "n" is het aantal elementen. Imaging dat u naar een item in een array wilt zoeken. Je zou elk element moeten bekijken en als "Ben jij het juiste element / item?" in het ergste geval bevindt het item zich in de laatste index, wat betekent dat het evenveel tijd kostte als er items in de lijst stonden, dus om generiek te zijn, zeggen we "oh hey, n is een redelijke gegeven hoeveelheid waarden!" .

Dus dan begrijp je misschien wat "n2"betekent, maar om nog specifieker te spelen, speel met de gedachte dat je een eenvoudige, de eenvoudigste sorteeralgoritme hebt: bubblesort. Dit algoritme moet voor elk item de hele lijst doornemen.

Mijn lijst

  1. 1
  2. 6
  3. 3

De stroom hier zou zijn:

  • Vergelijk 1 en 6, wat is het grootst? Oké 6 zit op de goede plek, vooruit!
  • Vergelijk 6 en 3, oh, 3 is minder! Laten we dat verplaatsen, Ok de lijst is veranderd, we moeten vanaf het begin beginnen!

Dit is O n2 omdat je naar alle items in de lijst moet kijken als er "n" items zijn. Voor elk item kijk je nogmaals naar alle items om te vergelijken, dit is ook "n", dus voor elk item kijk je "n" keer, wat betekent n * n = n2

Ik hoop dat dit zo simpel is als je het wilt.

Maar onthoud, Big O is slechts een manier om jezelf uit te drukken op de manier van tijd en ruimte.


77
2018-01-28 11:14



Big O beschrijft de fundamentele scaling aard van een algoritme.

Er is veel informatie die Big O niet over een bepaald algoritme vertelt. Het snijdt tot op het bot en geeft alleen informatie over de scaling aard van een algoritme, specifiek hoe het gebruik van de resource (denktijd of geheugen) van een algoritme schalen in reactie op de "input size".

Overweeg het verschil tussen een stoommachine en een raket. Het zijn niet alleen verschillende varianten van hetzelfde ding (zoals bijvoorbeeld een Prius-motor versus een Lamborghini-motor), maar het zijn dramatisch verschillende soorten voortstuwingssystemen, in hun kern. Een stoommachine kan sneller zijn dan een speelgoedraket, maar geen enkele stoommachine kan de snelheden van een orbitaal draagraket bereiken. Dit komt omdat deze systemen verschillende schaalkenmerken hebben met betrekking tot de relatie van de vereiste brandstof ("brongebruik") om een ​​gegeven snelheid te bereiken ("invoerformaat").

Waarom is dit zo belangrijk? Omdat software zich bezighoudt met problemen die in grootte kunnen verschillen met factoren tot een biljoen. Overweeg dat voor een moment. De verhouding tussen de snelheid die nodig is om naar de maan te reizen en de menselijke loopsnelheid is minder dan 10.000: 1, en dat is absoluut klein in vergelijking met het bereik in de invoerformaten waar software voor staat. En omdat software mogelijk te maken heeft met een astronomisch bereik in invoermaten, is er de potentie voor de Big O-complexiteit van een algoritme, het is een fundamenteel schalingskarakter, om uitvoeringsdetails te overtroeven.

Overweeg het canonieke sorteervoorbeeld. Belsortering is O (n2) terwijl merge-sort O is (n log n). Stel dat u twee sorteertoepassingen hebt, toepassing A die bellen-sorteren gebruikt en toepassing B die samenvoegtypen gebruikt, en laten we zeggen dat voor invoerformaten van ongeveer 30 elementen, toepassing A bij het sorteren 1.000 keer sneller is dan toepassing B. Als u nooit meer dan 30 elementen hoeft te sorteren, is het duidelijk dat u de voorkeur zou geven aan toepassing A, omdat deze bij deze invoerformaten veel sneller is. Als je echter vindt dat je misschien tien miljoen items moet sorteren, dan is wat je zou verwachten dat applicatie B in dit geval duizenden keer sneller zou zijn dan applicatie A, volledig vanwege de schaal van elk algoritme.


52
2018-01-28 13:12



Hier is het eenvoudige Engelse bestiarium dat ik gebruik bij het uitleggen van de gangbare variëteiten van Big-O

Geef in alle gevallen de voorkeur aan algoritmen die hoger in de lijst staan ​​dan die lager in de lijst. De kosten van overstappen naar een duurdere complexiteitsklasse variëren echter aanzienlijk.

O (1):

Geen groei. Ongeacht hoe groot het probleem is, u kunt het in dezelfde hoeveelheid tijd oplossen. Dit is enigszins analoog aan uitzendingen waarbij het evenveel energie kost om over een bepaalde afstand uit te zenden, ongeacht het aantal mensen dat binnen het uitzendbereik ligt.

O (log n):

Deze complexiteit is hetzelfde als O (1) behalve dat het gewoon een klein beetje erger is. Voor alle praktische doeleinden, kunt u dit beschouwen als een zeer grote constante schaal. Het verschil in werk tussen de verwerking van 1000 en 1 miljard items is slechts een factor zes.

O(n):

De kosten van het oplossen van het probleem zijn evenredig met de omvang van het probleem. Als uw probleem dubbel zo groot wordt, verdubbelen de kosten van de oplossing. Aangezien de meeste problemen op de een of andere manier in de computer moeten worden gescand, zoals gegevensinvoer, schijfuitlezing of netwerkverkeer, is dit over het algemeen een betaalbare schaalfactor.

O(n logboek n):

Deze complexiteit lijkt erg op O(n). Voor alle praktische doeleinden zijn de twee equivalent. Dit niveau van complexiteit wordt over het algemeen nog steeds als schaalbaar beschouwd. Door aannames aan te passen wat O(n logboek n) algoritmen kunnen worden omgezet in O(n) algoritmen. Als u de grootte van de toetsen begrenst, wordt het sorteren bijvoorbeeld beperkt O(n logboek n) naar O(n).

O(n2):

Groeit als een vierkant, waar n is de lengte van de zijkant van een vierkant. Dit is hetzelfde groeipercentage als het "netwerkeffect", waarbij iedereen in een netwerk iedereen in het netwerk kent. Groei is duur. Meest schaalbare oplossingen kunnen geen algoritmen gebruiken met dit niveau van complexiteit zonder significant gymnastiek te doen. Dit geldt in het algemeen voor alle andere veeltermcomplexiteiten - O(nk) - ook.

O (2n):

Schaalt niet. Je hebt geen hoop om een ​​probleem van niet-triviale omvang op te lossen. Handig om te weten wat te vermijden, en voor experts om benaderende algoritmen te vinden O(nk).


35
2018-01-27 23:09



Big O is een maat voor hoeveel tijd / ruimte een algoritme gebruikt in verhouding tot de grootte van de invoer.

Als een algoritme O (n) is, neemt de tijd / ruimte toe met dezelfde snelheid als de invoer.

Als een algoritme O (n2) dan neemt de tijd / ruimte toe met de snelheid van de invoer in het kwadraat.

enzovoort.


34
2018-01-28 11:19



Het is erg moeilijk om de snelheid van softwareprogramma's te meten, en wanneer we het proberen, kunnen de antwoorden heel complex zijn en worden gevuld met uitzonderingen en speciale gevallen. Dit is een groot probleem, want al die uitzonderingen en speciale gevallen zijn storend en nutteloos wanneer we twee verschillende programma's met elkaar willen vergelijken om erachter te komen welke "snelste" is.

Als resultaat van al deze nutteloze complexiteit proberen mensen de snelheid van softwareprogramma's te beschrijven met de kleinste en minst complexe (wiskundige) uitdrukkingen die mogelijk zijn. Deze uitdrukkingen zijn zeer ruwe benaderingen: hoewel ze met een beetje geluk de "essentie" zullen vangen van de vraag of een stuk van de software snel of langzaam is.

Omdat ze benaderingen zijn, gebruiken we de letter "O" (Big Oh) in de uitdrukking, als een conventie om aan de lezer te signaleren dat we een grove oversimplificatie maken. (En om ervoor te zorgen dat niemand ten onrechte denkt dat de uitdrukking op wat voor manier dan ook accuraat is).

Als je de "Oh" leest als "in de orde van" of "bij benadering", dan ga je niet teveel verkeerd. (Ik denk dat de keuze van de Big-Oh een poging tot humor was).

Het enige dat deze "Big-Oh" -uitdrukkingen proberen te doen, is beschrijven hoeveel de software langzamer werkt, omdat we de hoeveelheid gegevens die de software moet verwerken, vergroten. Als we de hoeveelheid gegevens die moet worden verwerkt verdubbelen, heeft de software dan twee keer zo lang nodig om het werk af te maken? Tien keer zo lang? In de praktijk zijn er een zeer beperkt aantal groot-Oh-expressies die u zult tegenkomen en waarover u zich zorgen moet maken:

De goede:

  • O(1)  Constante: Het programma heeft dezelfde tijd nodig om te werken, ongeacht hoe groot de invoer is.
  • O(log n)  logaritmische: De runtime van het programma neemt slechts langzaam toe, zelfs bij grote toenames in de grootte van de invoer.

De slechte:

  • O(n)  Lineair: De runtime van het programma neemt evenredig toe met de grootte van de invoer.
  • O(n^k)  Polynomial: - Verwerkingstijd groeit sneller en sneller - als een polynomiale functie - naarmate de invoer groter wordt.

... en de lelijke:

  • O(k^n)  exponentiële De runtime van het programma neemt zeer snel toe met zelfs bescheiden toename van de omvang van het probleem - het is alleen praktisch om kleine gegevenssets met exponentiële algoritmen te verwerken.
  • O(n!)  factorial De runtime van het programma zal langer zijn dan je je kunt veroorloven om te wachten op iets anders dan de allerkleinste en meest triviaal ogende datasets.

30
2018-05-29 13:51