Tényleg megérted Big O-t? Ha igen, akkor ez egy interjú előtt felfrissíti a megértését. Ha nem, ne aggódjon - gyere és csatlakozzon hozzánk a számítástechnika néhány törekvéséhez.
Ha elvégzett néhány algoritmussal kapcsolatos tanfolyamot, valószínűleg hallott a Big O jelölés kifejezésről . Ha még nem tette meg, itt áttekintjük, majd mélyebben megértjük, mi is valójában.
A Big O jelölés az egyik legalapvetőbb eszköz a számítástechnikusok számára az algoritmus költségeinek elemzéséhez. A szoftvermérnökök számára jó gyakorlat, ha az elmélyülést is megértik.
Ez a cikk azzal a feltevéssel íródott, hogy már megoldott valamilyen kódot. Ezenkívül néhány alapos anyag középiskolai matematikai alapismereteket is igényel, ezért kissé kevésbé lehet kényelmes a kezdők számára. De ha készen áll, kezdjük!
Ebben a cikkben mélyreható vitát folytatunk a Big O jelölésről. Először egy algoritmussal kezdjük, hogy megnyissuk megértésünket. Ezután elmegyünk egy kicsit a matematikába, hogy hivatalos megértésünk legyen. Ezután áttekintjük a Big O jelölés néhány gyakori változatát. Végül egy gyakorlati forgatókönyvben tárgyaljuk a Big O néhány korlátját. A tartalomjegyzék alább található.
Tartalomjegyzék
- Mi a Big O jelölés, és miért számít
- A Big O jelölés formális meghatározása
- Nagy O, Kis O, Omega és Theta
- A tipikus Big Os komplexitás összehasonlítása
- Idő és tér komplexitás
- Legjobb, átlagos, legrosszabb, várható összetettség
- Miért nem számít Big O?
- A végén…
Tehát kezdjük.
1. Mi a nagy O jelölés, és miért számít?
„A Big O jelölés egy matematikai jelölés, amely leírja a függvény korlátozó viselkedését, amikor az érv egy adott érték vagy végtelen felé mutat. Paul Bachmann, Edmund Landau és mások által feltalált jelölések családjának tagja, amelyeket együttesen Bachmann – Landau jelölésnek vagy aszimptotikus jelölésnek hívnak. ”- A Wikipédia meghatározása a Big O jelölésrőlEgyszerű szavakkal, a Big O jelölés leírja a kód összetettségét algebrai kifejezésekkel.
Hogy megértsük, mi a nagy O jelölés, megnézhetünk egy tipikus példát, az O (n²) -t, amelyet általában „Big O négyzet” -nek ejtenek . Az „n” betű itt jelöli a bemeneti méretet , az „O ()” belsejében található „g (n) = n²” függvény képet ad arról, hogy az algoritmus mennyire összetett a bemeneti mérethez képest.
Az O (n²) komplexitású tipikus algoritmus a szelekció rendezési algoritmus lenne. Selection sort egy válogatás algoritmus, amely végigmegy a listán, hogy biztosítsa minden eleme indexű i az i-edik legkisebb / legnagyobb eleme a listában. Az alábbi CODEPEN vizuális példát ad rá.
Az algoritmus a következő kóddal írható le. Annak érdekében, hogy ellenőrizze, hogy a i-edik elem az i-edik legkisebb eleme a listán, ez az algoritmus először végigmegy a listán egy hurok. Ezután minden elemhez használ egy másik ciklust, hogy megtalálja a legkisebb elemet a lista fennmaradó részében.
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) } }Ebben a forgatókönyvben a List változót tekintjük bemenetnek, így az n bemeneti méret a Listán belüli elemek száma . Tegyük fel, hogy az if utasítás és az if utasítás által határolt érték-hozzárendelés állandó időt vesz igénybe. Ezután megtalálhatjuk a SelectionSort függvény nagy O jelölését, elemezve, hogy az utasításokat hányszor hajtják végre.
Először a belső for ciklus n-szer futtatja az utasításokat. Aztán az i növekedése után a hurok belső része n-1-szer fut… ... amíg egyszer fut, majd mindkét for hurok eléri a befejezési feltételeket.
Ez végül geometriai összeget ad nekünk, és némi középiskolai matematikával azt tapasztalhatjuk, hogy a belső hurok 1 + 2 ... + n-szer megismétlődik, ami n (n-1) / 2-szer egyenlő. Ha ezt megszorozzuk, akkor n² / 2-n / 2-t kapunk.
Ha nagy O jelölést számolunk, akkor csak a domináns kifejezések törődnek velünk, és nem érdekelnek az együtthatók. Így az n²-t vesszük végső nagy O-nak. O-nak (n²) írjuk, amelyet ismét „Big O-négyzet” -nek ejtünk .
Most arra lehet kíváncsi, hogy miről is szól ez a „domináns kifejezés” ? És miért nem érdekelnek minket az együtthatók? Ne aggódj, egyenként át fogjuk őket nézni. Lehet, hogy az elején egy kicsit nehéz megérteni, de mindez sokkal értelmesebb lesz, amikor végigolvassa a következő részt.
2. A Big O jelölés formális meghatározása
Volt egyszer egy indiai király, aki egy bölcs embert akart megjutalmazni kiválóságáért. A bölcs nem kért mást, csak egy kis búzát, amely betöltött egy sakktáblát.
De itt voltak a szabályai: az első cserépben 1 szem búzát szeretne, majd 2-t a második csempére, majd 4-et a következőre ... a sakktáblán minden egyes lapot dupla mennyiségű szemcsével kellett kitölteni, mint előző egy. A naiv király habozás nélkül beleegyezett, azt gondolva, hogy triviális követelésnek kell eleget tennie, amíg ténylegesen nem folytatja és megpróbálja ...
Tehát hány szem búzával tartozik a bölcsnek a király? Tudjuk, hogy egy sakktáblának 8 és 8 négyzete van, ami összesen 64 csempét tartalmaz, tehát a végső lapon 2⁶⁴ szem búzának kell lennie. Ha online végez számítást, akkor 1,8446744 * 10¹⁹-t kap, azaz körülbelül 18-at, majd 18 nullát. Feltételezve, hogy minden búzaszem súlya 0,01 gramm, ez 184 467 440 737 tonna búzát jelent. És 184 milliárd tonna elég sok, nem?
A számok később meglehetősen gyorsan növekednek az exponenciális növekedés érdekében, nem igaz? Ugyanez a logika érvényes a számítógépes algoritmusokra is. Ha a feladat elvégzéséhez szükséges erőfeszítések exponenciálisan nőnek a bemeneti mérethez képest, akkor az hatalmasra válhat.
Most a 64 négyzet 4096. Ha ezt a számot hozzáadja a 2⁶⁴-hez, akkor az elveszik a számjegyeken kívül. Ezért, ha a növekedési ütemet nézzük, csak a domináns kifejezések törődnek velünk. És mivel a növekedést a bemeneti méret tekintetében szeretnénk elemezni, az együtthatók, amelyek csak a számot szorozzák meg, nem pedig a bemeneti méretet, nem tartalmaznak hasznos információkat.
Az alábbiakban a Big O formális meghatározása található:
A formális meghatározás akkor hasznos, ha matematikai bizonyítást kell végrehajtania. Például a szelekció rendezésének időbeli összetettségét az f (n) = n² / 2-n / 2 függvénnyel határozhatjuk meg, amint azt az előző szakaszban tárgyaltuk.
Ha megengedjük, hogy a g (n) függvényünk legyen n², akkor megtalálhatunk állandó c = 1 és N a = 0 értéket, és mindaddig, amíg N> N₀, N² mindig nagyobb lesz, mint N² / 2-N / 2. Könnyen bizonyíthatjuk ezt úgy, hogy mindkét funkcióból kivonjuk az N² / 2 értéket, és akkor könnyen láthatjuk, hogy N² / 2> -N / 2 igaz, amikor N> 0. Ezért arra a következtetésre juthatunk, hogy f (n) = O (n²), a másik választási sorrendben „nagy O négyzet”.
You might have noticed a little trick here. That is, if you make g(n) grow supper fast, way faster than anything, O(g(n)) will always be great enough. For example, for any polynomial function, you can always be right by saying that they are O(2ⁿ) because 2ⁿ will eventually outgrow any polynomials.
Mathematically, you are right, but generally when we talk about Big O, we want to know the tight bound of the function. You will understand this more as you read through the next section.
But before we go, let’s test your understanding with the following question. The answer will be found in later sections so it won’t be a throw away.
Kérdés: A képet 2D-s pixeltömb képviseli. Ha beágyazott hurokot használ az összes pixel végigviteléhez (vagyis van egy for for ciklus az összes oszlopon, majd egy másik a hurok belsejében, hogy az összes soron keresztül menjen), akkor mekkora az algoritmus időbeli összetettsége, amikor a képet tekintjük bemenetnek?3. Nagy O, Kis O, Omega és Theta
Nagy O: „f (n) O (g (n))” iff néhány c és N₀ konstans esetében, f (N) ≤ cg (N) minden N> N₀Omega esetében: „f (n) Ω (g ( n)) ”iff egyes c és N₀ konstansok esetén, f (N) ≥ cg (N) minden N> N₀Téta esetében:„ f (n) is Θ (g (n)) ”iff f (n) O (g) (n)) és f (n) Ω (g (n)) Kis O: „f (n) o (g (n))” iff f (n) O (g (n)) és f ( n) nem Θ (g (n)) - Big O, Omega, Theta és Little O formális meghatározásaEgyszerű szavakkal:
- 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érdés: A következő funkciók rangsorolása a legösszetettebbtől a bérleti komplexumig.
Megoldás a 2. szakaszhoz Kérdés: Valójában trükkös kérdés volt, hogy tesztelje megértését. A kérdés arra készteti Önt, hogy válaszoljon O (n²) -re, mert van beágyazva a hurok. Állítólag azonban n a bemeneti méret. Mivel a képtömb a bemenet, és minden pixelt csak egyszer iteráltak, a válasz valójában O (n). A következő szakasz további, ehhez hasonló példákat mutat be.
5. Idő és tér komplexitás
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.
A faktoriálok szorzókkal ábrázolhatók, és így a logaritmikus függvényen kívüli összeadásokká alakíthatók. Az „n választani 2” átalakítható polinommá, amelynek kubikus tagja a legnagyobb.
És végül sorolhatjuk a függvényeket a legösszetettebbtől a legkevésbé komplexig.
Miért nem számít a BigO?
!!! - FIGYELEM - !!! Az itt tárgyalt tartalmakat a világ legtöbb programozója általában nem fogadja el. Beszélje meg saját felelősségére egy interjúban. Az emberek valójában blogon arról, hogyan sikerült a Google interjúk, mert megkérdőjelezték a hatóság, mint itt. !!! - FIGYELEM - !!!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…
I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.
Hope you have a great time learning computer science!!!