이 소수 테스트 알고리즘의 시간 복잡도?

Question

나는이 숫자가 소수 여부를 결정 다음 코드를

public static boolean isPrime(int n){ 
    boolean answer = (n>1)? true: false; 

    for(int i = 2; i*i <= n; ++i) 
    { 
     System.out.printf("%d\n", i); 
     if(n%i == 0) 
     { 
      answer = false; 
      break; 
     } 
    } 
    return answer;  
} 

어떻게이 함수의 큰-O 시간 복잡도를 확인할 수 있습니까? 이 경우 입력의 크기는 얼마입니까?

Answer 1

이 함수의 최악의 런타임을 생각해보십시오.이 함수는 숫자가 실제로 소수 일 경우에 발생합니다. 이 경우 내부 루프는 가능한 한 여러 번 실행됩니다. 루프의 각 반복은 일정한 작업량을 수행하므로 수행되는 전체 작업은 O (루프 반복 횟수)가됩니다.

루프 반복 횟수는 얼마입니까? 의 루프 경계를 살펴 보자 :이 루프는만큼 내가 ² ≤ N 실행을 유지합니다

for(int i = 2; i*i <= n; ++i) 

공지있다. 따라서 루프는 i ≥ √ n + 1이 되 자마자 종료됩니다. 따라서 루프는 O (√ n) 번 실행되기 때문에 최악의 경우의 시간 복잡도는 O (√)입니다.

두 번째 질문에 대해 - 입력의 크기는 무엇입니까? - 일반적으로 소수 테스트 알고리즘 (또는 많은 수의 알고리즘)을 볼 때 입력의 크기는 입력을 기록하는 데 필요한 비트 수로 정의됩니다. 귀하의 경우, 숫자 n을 부여 받았으므로 n을 쓰는 데 필요한 비트 수는 Θ (log n)입니다. 즉,이 경우 "다항식 시간"은 O (로그 ^k n)와 같을 것입니다. O (√ n)는 O (로그 n) ^{1/2 1/2 1/2 문자로, 쓰기에 필요한 비트 수보다 지수가 더 큽니다 입력.}

희망이 도움이됩니다.