Algoritmer på almindelig engelsk: tidskompleksitet og Big-O-notation

Hver god udvikler har tid til at tænke. De vil give deres brugere mere af det, så de kan gøre alle de ting, de nyder. De gør dette ved at minimere tidskompleksitet .

Før du kan forstå tidskompleksitet i programmering, skal du forstå, hvor det oftest anvendes: i design af algoritmer .

Så hvad er en algoritme, alligevel?

Kort sagt, en algoritme er en række indeholdte trin, som du følger for at nå et mål eller for at producere noget output. Lad os f.eks. Tage din bedstemors opskrift på at bage en kage. Vent, tæller det som en algoritme? Det gør det bestemt!

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

Algoritmer er nyttige i vores undersøgelse af tidskompleksitet, fordi de kommer i alle former og størrelser.

På samme måde kan du skære en tærte på 100 forskellige måder, du kan løse et enkelt problem med mange forskellige algoritmer. Nogle løsninger er bare mere effektive, tager kortere tid og kræver mindre plads end andre.

Så hovedspørgsmålet er: hvordan skal vi analysere, hvilke løsninger der er mest effektive?

Matematik til undsætning! Analyse af tidskompleksitet i programmering er bare en ekstremt forenklet matematisk måde at analysere, hvor lang tid en algoritme med et givet antal input (n) vil tage for at fuldføre opgaven. Det defineres normalt ved hjælp af Big-O-notation .

Hvad er Big O notation, spørger du?

Hvis du lover, at du ikke vil give op og stoppe med at læse, vil jeg fortælle dig det.

Big-O-notation er en måde at konvertere de overordnede trin i en algoritme til algebraiske termer og derefter ekskludere konstanter og koefficienter af lavere orden, der ikke har så stor indflydelse på problemets samlede kompleksitet.

Matematikere vil sandsynligvis krympe lidt af min antagelse om "samlet effekt" der, men for udviklere at spare tid er det lettere at forenkle tingene på denne måde:

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

Kort sagt siger alt dette eksempel: vi ser kun på den faktor i vores udtryk, der har den potentielle største indflydelse på den værdi, som vores udtryk vil returnere. (Dette ændres, når konstanten bliver ekstremt stor, og n bliver lille, men lad os ikke bekymre os om det for nu).

Nedenfor er nogle almindelige tidskompleksiteter med enkle definitioner. Du er dog velkommen til at tjekke Wikipedia for mere detaljerede definitioner.

  • O (1) - Konstant tid: Givet et input af størrelse n, tager det kun et enkelt trin for algoritmen at udføre opgaven.
  • O (log n) - Logaritmisk tid: givet et input af størrelse n, reduceres antallet af trin, det tager for at udføre opgaven, med en eller anden faktor for hvert trin.
  • O (n) - Lineær tid: Givet et input af størrelse n, er antallet af nødvendige trin direkte relateret (1 til 1)
  • O (n²) - Kvadratisk tid: Givet et input af størrelse n, er antallet af trin, det tager for at udføre en opgave, kvadratisk på n.
  • O (C ^ n) - Eksponentiel tid: Givet et input af størrelse n, er antallet af trin, det tager for at udføre en opgave, konstant til n magten (ret stort antal).

Med denne viden i hånden kan vi se antallet af trin, som hver af disse tidskompleksiteter indebærer:

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 "(...)"

Som du kan se, kan ting let blive størrelsesordener mere komplekse afhængigt af kompleksiteten af ​​din algoritme. Heldigvis er computere stærke nok til stadig at håndtere virkelig store kompleksiteter relativt hurtigt.

Så hvordan skal vi analysere vores kode med Big-O notation?

Nå her er nogle hurtige og enkle eksempler på, hvordan du kan anvende denne viden til algoritmer, du måske støder på i naturen eller kode op selv.

Vi bruger nedenstående datastrukturer til vores eksempler:

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

O (1) - Konstant tid

Værdiopslag, når du kender nøglen (objekter) eller indekset (arrays) tager altid et skridt og er således konstant tid.

//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) - Logaritmisk tid

Hvis du ved, hvilken side af arrayet du skal se efter et element, sparer du tid ved at skære den anden halvdel ud.

//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ær tid

Du skal se på hvert element i arrayet eller listen for at udføre opgaven. Enkelt for sløjfer er næsten altid lineær tid. Også matrixmetoder som indexOf er også lineær tid. Du er bare abstraheret væk fra looping-processen.

//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²) - Kvadratisk tid

Indlejret til sløjfer er kvadratisk tid, fordi du kører en lineær operation inden for en anden lineær operation (eller n * n = n²).

//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) - Eksponentiel tid

Eksponentiel tid er normalt i situationer, hvor du ikke ved så meget, og du er nødt til at prøve enhver mulig kombination eller permutation.

//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

Du skal lave tidskompleksitetsanalyse, når som helst du skriver kode, der skal køre hurtigt.

Når du har forskellige ruter til at løse et problem, er det bestemt klogere at skabe en løsning, der bare fungerer først. Men i det lange løb vil du have en løsning, der kører så hurtigt og effektivt som muligt.

For at hjælpe dig med problemløsningsprocessen er her nogle enkle spørgsmål at stille:

1. Løser dette problemet? Ja =>

2. Har du tid til at arbejde på dette

Ja => gå til trin 3

Nej => Kom tilbage til det senere og gå til trin 6 for nu.

3. Dækker det alle kantkasser? Ja =>

4. Er mine kompleksiteter så lave som muligt?

Nej => omskriv eller rediger til en ny løsning -> gå tilbage til trin 1

Ja => gå til trin 5

5. Er min kode TØR? Ja =>

6. Glæd dig!

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) - Lineær tid: Antallet af nødvendige trin er direkte relateret (1 til 1).
  • O (n²) - Kvadratisk tid: Antallet af trin, det tager at udføre en opgave, er kvadratisk på n.
  • O (C ^ n) - Eksponentielt: Antallet af trin, det tager for at udføre en opgave, er konstant til n magten (stort antal).

Og her er nogle nyttige ressourcer til at lære mere:

  • Wikipedia
  • Big O Cheat Sheet er en stor ressource med almindelige algoritmiske tidskompleksiteter og en grafisk repræsentation. Tjek det ud!