jos olet viettänyt aikaa code wars, löytää jos Numero on prime on yhteinen teema joukossa luokan ongelmia. Kun aloitin koodaus ajattelin silmukointi läpi kaikki numerot 1 num ja tarkistaa, jos se oli jaollinen oli hyvä lähestymistapa. Mutta heti kun sain tietää big O notationista, olin häpeissäni!

muutamien tutkimusten ja wiki-lukemien jälkeen löysin tänä viikonloppuna loistavan funktion selvittää, onko luku alkuluku, jossa on sub-lineaarinen O(n) – aika. Seuraava toiminto on ratkaisu löysin:

function isPrime (num) {
if (num <= 1) {
return true
} else if (num <= 3) {
return true
} else if (num%2 === 0 || num%3 === 0) {
return false
}
let i = 5
while (i*i <= num) {
if (num%i === 0 || num%(i+2) === 0) {
return false
}
i += 6
}
return true
}
  1. tarkistaa, onko numero 0, 1 vai negatiivinen. Palautetaan true, jos luku on tällä alueella.
  2. tarkistaa, onko numero 2 vai 3. Palaa true, jos Numero on 2 tai 3.
  3. viimeinen if lauseke palauttaa, että luku ei ole alkuluku, jos se on jaollinen 2: lla tai 3: lla.
  4. tämän funktion viimeinen osa on kinkkisin-while loop! Se on lähinnä tarkistaa jokainen pariton määrä, joka ei ole jaollinen 3, kunnes se tulee suurempi kuin neliöjuuri, num. Esimerkiksi ensimmäiset i ja i + 2 ovat 5 ja 7. Seuraavat i ja i + 2 ovat sijoilla 11 ja 13. Se ei tarkista 9: ää tai 15: tä, koska molemmat ovat jaollisia 3: lla ja olisivat jääneet kiinni viimeisessä else if lauseessa.
  5. palauttaa lopulta true, jos luku ei ollut jaollinen millään i tai i+2 merkinnöillä, koska luku on alkuluku.

O(n)

jos oletamme, että n on isprime: iin siirretty luku, alkuperäisen lähestymistapani O(n) olisi O (n). Siksi tällä kertaa monimutkaisuus olisi lineaarinen. Tämä on hieno, jos kaikki olet tekemässä on tarkistaa, mutta monta kertaa tämä toiminto on auttajafunktio ja tarkistaa, jos numeroluettelo on prime olisi eksponentiaalinen.

edellä mainittu funktio isPrime olisi O (n^1/2). Tämä tarkoittaa, että aikakompleksisuus on sub-lineaarinen, mikä vähentää huomattavasti suuremman funktion aikakompleksisuutta.

Loppupäätelmässä