Mis on selgitatud suurt O-tähistust: ruumi ja aja keerukus

Kas sa mõistad tõesti suurt O-d? Kui jah, siis värskendab see teie mõistmist enne intervjuud. Kui ei, siis ärge muretsege - tulge meiega kaasa arvutiteaduse mõningate ettevõtmiste jaoks.

Kui olete läbinud mõned algoritmidega seotud kursused, olete ilmselt kuulnud terminist Big O notatsioon . Kui te pole seda teinud, vaatame selle siin üle ja saame siis sügavamalt aru, mis see tegelikult on.

Big O tähistamine on arvutiteadlaste jaoks üks põhilisemaid vahendeid algoritmi maksumuse analüüsimiseks. Tarkvarainseneride jaoks on hea tava mõista ka süvitsi.

See artikkel on kirjutatud eeldusel, et olete juba mõne koodiga tegelenud. Samuti nõuab mõni põhjalik materjal ka keskkooli matemaatika aluseid ja võib seetõttu olla algajatele pisut vähem mugav. Aga kui olete valmis, alustame!

Selles artiklis on meil põhjalik arutelu Big O tähistamise üle. Alustame arusaamise avamiseks algoritmi näitest. Seejärel läheme veidi matemaatikasse, et saada ametlik arusaam. Pärast seda vaatame läbi mõned üldised variatsioonid Big O tähistamisest. Lõpuks arutame praktilise stsenaariumi korral mõningaid Big O piiranguid. Sisukorra leiate allpool.

Sisukord

  1. Mis on Big O tähis ja miks see oluline on
  2. Suure O tähistuse ametlik määratlus
  3. Suur O, väike O, Omega & Theta
  4. Tüüpiliste suurte osade keerukuse võrdlus
  5. Aja ja ruumi keerukus
  6. Parim, keskmine, halvim, oodatav keerukus
  7. Miks Big O pole oluline
  8. Lõpuks…

Nii et alustame.

1. Mis on suur O tähistamine ja miks see oluline on

„Suur O tähistamine on matemaatiline tähistus, mis kirjeldab funktsiooni piiravat käitumist, kui argument kaldub kindla väärtuse või lõpmatuse poole. See on Paul Bachmanni, Edmund Landau ja teiste väljamõeldud noodiperekonna liige, mida ühiselt nimetatakse Bachmann – Landau noodideks või asümptootilisteks nootideks. ”- Vikipeedia määratlus Big O noodist

Lihtsate sõnadega kirjeldab Big O tähistamine teie koodi keerukust algebraliste terminite abil.

Mõistmaks, mis on suur O tähis, võime heita pilgu tüüpilisele näitele O (n²) , mida tavaliselt hääldatakse “suureks O ruuduks” . Kirjas "n" näitab siin sisend suurus ja funktsioon "g (n) = n²" sees "O ()" annab meile aimu, kuidas keerulise algoritmi suhtes sisend suurus.

Tüüpiline algoritm, millel on O (n²) keerukus, oleks valiku sorteerimise algoritm. Valiksortimine on sorteerimisalgoritm et kordub läbi nimekirja tagada iga element indeksiga i on i-nda väikseim / suurim element nimekirja. Allpool olev CODEPEN toob selle visuaalse näite.

Algoritmi saab kirjeldada järgmise koodiga. Veendumaks, et i-s element on loendi i-s väikseim element, kordab see algoritm kõigepealt loendi kaudu for-silmusega. Seejärel kasutab see iga elemendi jaoks silmuse jaoks teist, et leida loendi ülejäänud osast väikseim element.

SelectionSort(List) { for(i from 0 to List.Length) { SmallestElement = List[i] for(j from i to List.Length) { if(SmallestElement > List[j]) { SmallestElement = List[j] } } Swap(List[i], SmallestElement) } }

Selles stsenaariumis loeme sisendiks muutujat List , seega sisendi suurus n on loendis olevate elementide arv . Oletame, et if-lause ja if-lausega piiratud väärtuse omistamine võtab pidevalt aega. Siis leiame funktsiooni SelectionSort suure O-tähistuse, analüüsides, mitu korda avaldusi täidetakse.

Kõigepealt käivitab tsükli sisemine väited n korda. Ja siis, kui i on suurendatud, töötab tsükli sisemine osa n-1 korda ... ... kuni see töötab üks kord, siis jõuavad mõlemad for-silmuse lõpptingimused.

See annab lõpuks geomeetrilise summa ja mõne keskkooli matemaatika korral leiame, et sisemine silmus kordub 1 + 2… + n korda, mis võrdub n (n-1) / 2 korda. Kui selle välja korrutada, saame lõpuks n² / 2-n / 2.

Suure O-tähistuse arvutamisel hoolivad ainult domineerivad terminid ja koefitsiendid. Seega võtame n² oma viimaseks suureks O-ks. Kirjutame selle kui O (n²), mida jälle hääldatakse "suureks O ruuduks" .

Nüüd võite mõelda, mis see "domineeriv mõiste" üldse on? Ja miks meid koefitsiendid ei huvita? Ärge muretsege, me läheme neist ükshaaval üle. Alguses on sellest võib-olla natuke raske aru saada, kuid järgmisel lõigul lugedes on see kõik palju mõistlikum.

2. Suure O tähistuse ametlik määratlus

Kunagi oli üks India kuningas, kes tahtis tarka meest tubliduse eest premeerida. Tark mees ei palunud muud kui nisu, mis täidaks malelaua.

Kuid siin olid tema reeglid: esimeses plaadis soovib ta 1 tera nisu, siis 2 teist, siis 4 järgmist ... iga malelaua plaat pidi olema täidetud kahekordse teraviljaga kui eelmine üks. Naiivne kuningas nõustus kõhklemata, arvates, et selle täitmine on tühine nõue, kuni ta tegelikult edasi proovis ...

Niisiis, mitu nisutera on kuningas targale võlgu? Me teame, et malelauas on 8 ruutu 8 ruutu, mis on kokku 64 plaati, nii et viimasel plaadil peaks olema 2⁶⁴ tera nisu. Kui teete arvutuse veebis, saate lõpuks 1,8446744 * 10¹, see tähendab umbes 18, millele järgneb 18 nulli. Eeldades, et iga nisutera kaal on 0,01 grammi, annab see meile 184 467 440 737 tonni nisu. Ja 184 miljardit tonni on üsna palju, kas pole?

Eksponentsiaalse kasvu jaoks kasvavad numbrid hiljem üsna kiiresti? Sama loogika kehtib ka arvutialgoritmide kohta. Kui ülesande täitmiseks vajalikud jõupingutused sisendi suuruse suhtes hüppeliselt kasvavad, võib see lõpuks tohutult suureks minna.

Nüüd on ruut 64 4096. Kui lisate selle arvu 2⁶⁴-le, läheb see kaotsi väljaspool olulisi numbreid. Seetõttu hoolitseme kasvutempot vaadates ainult domineerivatest terminitest. Ja kuna me tahame analüüsida kasvu sisendi suuruse suhtes, ei sisalda koefitsiendid, mis ainult korrutavad arvu, mitte aga sisendi suurusega, kasulikku teavet.

Allpool on Big O ametlik määratlus:

Ametlik määratlus on kasulik, kui peate sooritama matemaatikatõendi. Näiteks saab valiku sorteerimise ajalise keerukuse määratleda funktsiooniga f (n) = n² / 2-n / 2, nagu me eelmises osas arutlesime.

Kui lubame oma funktsioonil g (n) olla n², võime leida konstandi c = 1 ja N₀ = 0 ning seni, kuni N> N₀, on N² alati suurem kui N² / 2-N / 2. Saame seda hõlpsalt tõestada, lahutades mõlemast funktsioonist N² / 2, siis näeme N² / 2> -N / 2 tõesena, kui N> 0. Seetõttu võime jõuda järeldusele, et f (n) = O (n²), teises valikus on sort "suur O ruudus".

Võib-olla olete siin märganud väikest trikki. See tähendab, et kui panete g (n) õhtusöögi kasvama kiiresti, kiiremini kui miski muu, on O (g (n)) alati piisavalt suur. Näiteks mis tahes polünoomifunktsiooni puhul võib teil alati õigus olla, öeldes, et nad on O (2ⁿ), sest 2ⁿ kasvab lõpuks kõikidest polünoomidest välja.

Matemaatiliselt on teil õigus, kuid üldiselt, kui räägime suurest O-st, tahame teada funktsiooni tihedat seost . Järgmisest jaotisest lugedes saate sellest rohkem aru.

Kuid enne kui läheme, proovime teie mõistmist järgmise küsimusega. Vastus leitakse hilisematest osadest, nii et see pole viske kaugusel.

Küsimus: pilti esindab 2D pikslite massiiv. Kui kasutate iga piksli iteratsiooniks pesastatud tsüklit (st teil on for for silmus läbimas kõik veerud, siis teine ​​silmus sees, et läbida kõik read), siis milline on algoritmi ajaline keerukus, kui pilti peetakse sisendiks?

3. Suur O, Väike O, Omega & Theta

Suur O: „f (n) on O (g (n))” iff mõne konstandi c ja N₀ korral, f (N) ≤ cg (N) kõigi N> N₀Omega puhul: „f (n) on Ω (g ( n)) ”iff mõnede konstantide c ja N₀ korral, f (N) ≥ cg (N) kõigi N> N₀Teta puhul:“ f (n) on Θ (g (n)) ”iff f (n) on O (g (n)) ja f (n) on Ω (g (n)) Väike O: “f (n) on o (g (n))” iff f (n) on O (g (n)) ja f ( n) ei ole Θ (g (n)) - Suure O, Oomega, Teeta ja Väikese O ametlik määratlus

Selgelt öeldes:

  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
  • Theta (Θ()) describes the exact bound of the complexity.
  • Little O (o()) describes the upper bound excluding the exact bound.

For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

But which function grows faster than the others? There are actually quite a few rules.

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n * log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n * n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the lease complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

Küsimus: järjestage järgmised funktsioonid kõige keerukamast rendikompleksini. Lahendus 2. jaotisele Küsimus: see oli tegelikult mõeldud trikiküsimuseks, et teie mõistmist proovile panna. Küsimus üritab panna teid vastama O (n²) -le, kuna seal on sisestatud silmus. Siiski eeldatakse, et n on sisendi suurus. Kuna sisend on pildimassiiv ja iga pikslit kordati ainult ühe korra, on vastus tegelikult O (n). Järgmises jaotises käsitletakse rohkem sarnaseid näiteid.

5. Aja ja ruumi keerukus

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n * log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to lease complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

Faktooriumi saab korrutada ja seega saab teisendada logaritmilisest funktsioonist väljapoole jäävateks liitmisteks. „N valige 2” saab teisendada polünoomiks, kusjuures kuuptermin on suurim.

Ja lõpuks saame järjestada funktsioonid kõige keerukamast kõige vähem keerukaks.

Miks BigO pole oluline

!!! - HOIATUS - !!! Siin käsitletud sisu ei aktsepteeri enamik maailma programmeerijaid. Arutage seda intervjuus omal vastutusel . Inimesed blogisid tegelikult sellest, kuidas nad oma Google'i intervjuudes ebaõnnestusid, kuna nad küsisid ametiasutust nagu siin. !!! - HOIATUS - !!!

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

Mulle meeldib kodeerida, õppida uusi asju ja jagada neid kogukonnaga. Kui teil on midagi, mis teid eriti huvitab, andke mulle sellest teada. Kirjutan üldiselt veebidisaini, tarkvaraarhitektuuri, matemaatika ja andmeteaduse teemadel. Kui olete huvitatud mõnest ülaltoodud teemast, võite leida mõned suurepärased artiklid, mida olen varem kirjutanud.

Loodetavasti on teil arvutiteaduste õppimisel tore aeg !!!