코드 전쟁에 시간을 보냈다면 숫자가 소수인지 찾는 것이 문제의 범주 사이에서 공통된 주제입니다. 처음 코딩을 시작했을 때 나는 모든 숫자 1 을 숫자로 반복하고 그것이 나눌 수 있는지 확인하는 것이 훌륭한 접근법이라고 생각했습니다. 그러나,내가 빅 오 표기법에 대해 알게 되 자마자 나는 굴욕 당했다!

이번 주말에 몇 가지 연구와 위키 독서를 한 후에,나는 숫자가 하위 선형으로 소수인지 여부를 찾는 훌륭한 기능을 발견했습니다. 다음 함수는 내가 찾은 솔루션입니다:

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. 숫자가 0,1 또는 음수인지 확인합니다. 숫자가 이 범위 내에 있는 경우true을 반환합니다.
  2. 번호가 2 또는 3 인지 확인합니다. 숫자가 2 또는 3 인 경우true을 반환합니다.
  3. 마지막if문은 2 또는 3 으로 나눌 수있는 경우 숫자가 소수가 아니라는 것을 반환합니다.
  4. 이 함수의 마지막 부분은 가장 까다 롭습니다. 이 숫자의 제곱근보다 큰 될 때까지 그것은 본질적으로 3 으로 나눌 수없는 모든 홀수를 확인한다. 예를 들어 첫 번째ii + 2은 5 와 7 입니다. 다음ii + 2은 11 과 13 이 될 것입니다. 둘 다 3 으로 나눌 수 있고 마지막else if문에서 잡혔기 때문에 9 또는 15 를 확인하지 않습니다.
  5. 숫자가 소수이기 때문에 숫자가i또는i+2항목으로 나눌 수없는 경우 마지막으로true을 반환합니다.

O(n)

면 우리 가정의 n 번호로 전달되 isPrime,O(n)의 초기 방법이 될 것입 O(n). 따라서이 시간 복잡성은 선형이 될 것입니다. 이것은 당신이하고있는 모든 것이 체크 인 경우 괜찮지 만,이 함수는 도우미 함수이며 숫자 목록이 소수인지 확인하는 것은 지수가 될 것입니다.

위의 함수isPrime은 영형(엔^1/2). 즉,시간 복잡도는 하위 선형이므로 더 큰 함수의 시간 복잡도가 크게 줄어 듭니다.

결론