Algoritmusok egyszerű angol nyelven: idő komplexitás és Big-O jelölés

Minden jó fejlesztőnek van ideje a fejében. Többet akarnak adni a felhasználóiknak, hogy mindazt megtegyék, amit élveznek. Ezt úgy teszik meg, hogy minimalizálják az idő összetettségét .

Mielőtt megérti a programozás időbeli összetettségét, meg kell értenie, hol alkalmazzák a leggyakrabban: az algoritmusok tervezésénél .

Tehát mi az algoritmus?

Egyszerűen fogalmazva: az algoritmus egy tartalmazott lépéssorozat, amelyet valamilyen cél elérése vagy valamilyen kimenet előállítása érdekében követ. Vegyük például a nagyi receptjét sütemény sütésére. Várjon, ez algoritmusnak számít? Persze, hogy megteszi!

function BakeCake(flavor, icing){ " 1. Heat Oven to 350 F 2. Mix flour, baking powder, salt 3. Beat butter and sugar until fluffy 4. Add eggs. 5. Mix in flour, baking powder, salt 6. Add milk and " + flavor + " 7. Mix further 8. Put in pan 9. Bake for 30 minutes 10." + if(icing === true) return 'add icing' + " 10. Stuff your face " } BakeCake('vanilla', true) => deliciousness

Az algoritmusok azért hasznosak az időbonyolultság vizsgálatában, mert minden formában és méretben kaphatók.

Ugyanígy 100 különböző módon szeletelhetünk egy tortát, és megoldhatunk egyetlen feladatot sokféle algoritmussal. Néhány megoldás csak hatékonyabb, kevesebb időt vesz igénybe és kevesebb helyet igényel, mint mások.

Tehát a fő kérdés: hogyan lehet elemezni a leghatékonyabb megoldásokat?

Matek a mentéshez! Az időbonyolultság-elemzés a programozásban csak egy rendkívül leegyszerűsített matematikai módszer annak elemzésére, hogy egy adott számú bemenettel (n) rendelkező algoritmus mennyi ideig tart a feladat elvégzéséhez. Általában Big-O jelöléssel határozható meg .

Mi a nagy O jelölés, kérdezed?

Ha megígéred, hogy nem adod fel, és abbahagyod az olvasást, akkor elmondom.

A Big-O jelölés egy algoritmus általános lépéseinek algebrai kifejezésekké történő átalakításának módja, majd kizárja azokat az alacsonyabb rendű állandókat és együtthatókat, amelyeknek nincs olyan nagy hatása a probléma általános összetettségére.

A matematikusok valószínűleg kissé meghúzódnak az ottani „általános hatás” feltételezésemtől, de a fejlesztők számára, hogy időt spóroljanak, könnyebb így egyszerűsíteni a dolgokat:

Regular Big-O 2 O(1) --> It's just a constant number 2n + 10 O(n) --> n has the largest effect 5n^2 O(n^2) --> n^2 has the largest effect

Röviden, mindez a példa azt mondja: csak azt a tényezőt vesszük figyelembe a kifejezésünkben, amely a legnagyobb hatást gyakorolja arra az értékre, amelyet kifejezésünk meg fog hozni. (Ez változik, mivel az állandó rendkívül nagy lesz, és n kicsi lesz, de most ne aggódjunk emiatt).

Az alábbiakban bemutatunk néhány általános időbeli bonyolultságot egyszerű definíciókkal. Nyugodtan nézze meg a Wikipédiát, még részletesebb meghatározásokért.

  • O (1) - Állandó idő: Adva egy n méretű bemenetet, csak egy lépésre van szükség ahhoz, hogy az algoritmus elvégezze a feladatot.
  • O (log n) - Logaritmikus idő: ha egy n méretű bemenetet ad meg, akkor a feladat elvégzéséhez szükséges lépések számát minden tényező bizonyos tényezővel csökkenti.
  • O (n) - Lineáris idő: Adva egy n méretű bemenetet, a szükséges lépések száma közvetlenül összefügg (1: 1)
  • O (n²) - Másodlagos idő: Adva egy n méretű bemenetet, a feladat végrehajtásához szükséges lépések száma n négyzet.
  • O (C ^ n) - Exponenciális idő: Adva egy n méretű bemenetet, a feladatok elvégzéséhez szükséges lépések száma állandó az n teljesítményhez képest (elég nagy szám).

Ez a tudás birtokában megtekintheti az egyes időbeli bonyolultságokkal járó lépések számát:

let n = 16; O (1) = 1 step "(awesome!)" O (log n) = 4 steps "(awesome!)" -- assumed base 2 O (n) = 16 steps "(pretty good!)" O(n^2) = 256 steps "(uhh..we can work with this?)" O(2^n) = 65,536 steps "(...)"

Amint láthatja, a dolgok könnyen nagyságrendekkel bonyolultabbá válhatnak, az algoritmus bonyolultságától függően. Szerencsére a számítógépek elég nagyok ahhoz, hogy viszonylag gyorsan kezeljék az igazán nagy összetettségeket.

Tehát hogyan folytassuk a kódunk elemzését Big-O jelöléssel?

Nos, íme néhány gyors és egyszerű példa arra, hogyan alkalmazhatja ezeket a tudásokat olyan algoritmusokra, amelyekkel a vadonban találkozhat, vagy kódolhatja magát.

Az alábbi adatszerkezeteket használjuk példáinkra:

var friends = { 'Mark' : true, 'Amy' : true, 'Carl' : false, 'Ray' : true, 'Laura' : false, } var sortedAges = [22, 24, 27, 29, 31]

O (1) - állandó idő

Az értékkeresés, ha tudja, hogy a kulcs (objektumok) vagy az index (tömbök) mindig egy lépést tesznek, így állandó idő.

//If I know the persons name, I only have to take one step to check: function isFriend(name){ //similar to knowing the index in an Array return friends[name]; }; isFriend('Mark') // returns True and only took one step function add(num1,num2){ // I have two numbers, takes one step to return the value return num1 + num2 }

O (log n) - logaritmikus idő

Ha tudja, hogy a tömb melyik oldalán kell keresnie egy elemet, időt takaríthat meg, ha kivágja a másik felét.

//You decrease the amount of work you have to do with each step function thisOld(num, array){ var midPoint = Math.floor( array.length /2 ); if( array[midPoint] === num) return true; if( array[midPoint]  only look at second half of the array if( array[midpoint] > num ) --> only look at first half of the array //recursively repeat until you arrive at your solution } thisOld(29, sortedAges) // returns true //Notes //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation. //This solution works because our Array is sorted //Recursive solutions are often logarithmic //We'll get into recursion in another post!

O (n) - Lineáris idő

A feladat végrehajtásához meg kell néznie a tömb vagy a lista minden elemét. A hurkokhoz tartozó single szinte mindig lineáris idő. Az olyan tömb módszerek, mint az indexOf , szintén lineáris idő. Csak elvonultál a hurokfolyamattól.

//The number of steps you take is directly correlated to the your input size function addAges(array){ var sum = 0; for (let i=0 ; i < array.length; i++){ //has to go through each value sum += array[i] } return sum; } addAges(sortedAges) //133

O (n²) - másodfokú idő

Beágyazott hurkok vannak négyzetes időben, mert már fut egy lineáris művelet keretében egy másik lineáris művelet (vagy n * n = Nl).

//The number of steps you take is your input size squared function addedAges(array){ var addedAge = []; for (let i=0 ; i < array.length; i++){ //has to go through each value for(let j=i+1 ; j < array.length ; j++){ //and go through them again addedAge.push(array[i] + array[j]); } } return addedAge; } addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ] //Notes //Nested for loops. If one for loop is linear time (n) //Then two nested for loops are (n * n) or (n^2) Quadratic!

O (2 ^ n) - Exponenciális idő

Az exponenciális idő általában olyan helyzetekre vonatkozik, amikor nem tudsz annyit, és minden lehetséges kombinációt vagy permutációt ki kell próbálnod.

//The number of steps it takes to accomplish a task is a constant to the n power //Thought example //Trying to find every combination of letters for a password of length n

Bármikor el kell végeznie az idő bonyolultsági elemzését, amikor gyorsan futtatandó kódot ír.

Ha különféle útvonalak vannak a probléma megoldására, mindenképpen bölcsebb egy olyan megoldást létrehozni, amely csak először működik. Hosszú távon azonban olyan megoldást szeretne, amely a lehető leggyorsabban és hatékonyabban fut.

Az alábbiakban felsorolunk néhány egyszerű kérdést, amely segítséget nyújt a problémamegoldás folyamatában:

1. Megoldja ez a problémát? Igen =>

2. Van-e ideje ezen dolgozni

Igen => folytassa a 3. lépéssel

Nem => Térjen vissza később, és folytassa a 6. lépéssel.

3. Minden éltestet lefed? Igen =>

4. A lehető legkisebb a komplexitásom?

Nem => átírni vagy módosítani új megoldássá -> visszatérni az 1. lépésre

Igen => folytassa az 5. lépéssel

5. A kódom SZÁRAZ? Igen =>

6. Örüljetek!

No => Make it D.R.Y, then rejoice!

Analyze time complexity any and all times you are trying to solve a problem. It’ll make you a better developer in the log run. Your teammates and users will love you for it.

Again, most problems you will face as programmer — whether algorithmic or programmatic — will have tens if not hundreds of ways of solving it. They may vary in how they solve the problem, but they all still solve that problem.

You could be making decisions between whether to use sets or graphs to store data. You could be deciding whether or not to use Angular, React, or Backbone for a team project. All of these solutions solve the same problem in a different way.

Given this, it’s hard to say there is a single “right” or “best” answer to these problems. But it is possible to say there are “better” or “worse” answers to a given problem.

Using one of our previous examples, it might be better to use React for a team project if half your team has experience with it, so it’ll take less time to get up and running.

The ability to describe a better solution usually springs from some semblance of time complexity analysis.

In short, if you’re going to solve a problem, solve it well. And use some Big-O to help you figure out how.

Here’s a final recap:

  • O(1) — Constant Time: it only takes a single step for the algorithm to accomplish the task.
  • O(log n) — Logarithmic Time: The number of steps it takes to accomplish a task are decreased by some factor with each step.
  • O(n) — Linear Time: The number of of steps required are directly related (1 to 1).
  • O(n²) — Quadratic Time: The number of steps it takes to accomplish a task is square of n.
  • O(C^n) — Exponential: The number of steps it takes to accomplish a task is a constant to the n power (pretty large number).

And here are some helpful resources to learn more:

  • Wikipedia
  • The Big O Cheat Sheet is a great resource with common algorithmic time complexities and a graphical representation. Check it out!