hvis du har brugt nogen tid på kode krige, at finde, hvis et tal er prime er et fælles tema blandt en kategori af problemer. Da jeg først begyndte at kode, tænkte jeg at løbe gennem alle numre 1 til num og kontrollere, om det var deleligt, var en god tilgang. Men så snart jeg lærte om big O notation, blev jeg mortificeret!

efter nogle undersøgelser og læsning i helgen fandt jeg en god funktion til at finde ud af, om et tal er prime med en sub-lineær O(n) tid. Følgende funktion er den løsning, jeg fandt:

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. kontrollerer, om tallet er 0, 1 eller negativt. Vender tilbage true hvis nummeret er inden for dette interval.
  2. kontrollerer, om tallet er 2 eller 3. Vender tilbage true hvis tallet er 2 eller 3.
  3. den sidste if erklæring returnerer, at tallet ikke er primtal, hvis det kan deles med 2 eller 3.
  4. den sidste del af denne funktion er den vanskeligste — Mens loop! Det kontrollerer i det væsentlige hvert ulige tal, der ikke kan deles med 3, indtil det bliver større end kvadratroden af num. For eksempel vil den første i og i + 2 være 5 og 7. Den næste i og i + 2 bliver 11 og 13. Det kontrollerer ikke 9 eller 15, fordi begge er delelige med 3 og ville være blevet fanget i den sidste else if erklæring.
  5. returnerer endelig true hvis tallet ikke var deleligt med nogen i eller i+2 poster, fordi tallet er primtal.

O(n)

hvis vi antager, at n er antallet, der overføres til isPrime, ville o(n) af min oprindelige tilgang være O(n). Derfor ville denne gang kompleksitet være lineær. Dette er fint, hvis alt hvad du laver er checken, men mange gange er denne funktion en hjælperfunktion, og det ville være eksponentielt at kontrollere, om en liste med tal er prime.

ovenstående funktion isPrime ville være O(n^1/2). Dette betyder, at tidskompleksiteten vil være sublinær, hvilket i høj grad vil reducere tidskompleksiteten for en større funktion.

Afslutningsvis