범위 내에서 소수 인쇄의 시간 복잡성?
-
29-09-2020 - |
문제
이 질문에 대한 답변을 썼습니다.
Prime Numbers에서 start
로 인쇄하는 주어진 코드의 시간 복잡성은 무엇입니까? $ o (end * \ sqrt {n}) $
/**
* Print prime numbers between start and end inputs
* Time-Complexity: O(end * sqrt(n))
* Space-Complexity: O(1) only one value as input
* @param start, end
* @return
*/
public void printPrimeSeries(int start, int end) {
for (int i = start; i < end; i++) {
if (findPrimeOrNot(i)) {
System.out.println("The value " + i + " is a prime number");
}
}
}
public boolean findPrimeOrNot(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter start number for prime:");
int startInput = scanner.nextInt();
System.out.println("Enter end number for prime:");
int endInput = scanner.nextInt();
PrimeNoSeries primeNoSeries = new PrimeNoSeries();
primeNoSeries.printPrimeSeries(startInput, endInput);
}
.
주의 사항 : 내 코드가 아닙니다. Mahesh87 .
내 대답은 다음과 같습니다.
$ n $ 은 end
입니다. $ o $ 표기법 $ n $ 은 end - start
와 start
사이의 범위 인 문제의 크기를 나타냅니다. 너의 경우. $ o $ 표기법 최악의 경우에 관심이 있으므로 end
가 항상 start
임을 가정 할 수 있습니다. 이제 $ n $ 은 0
의 별칭입니다.
$ n $ 을 정의 했으므로 end
가 $ o (n) $ (printPrimeSeries
에서 0
로부터). 이 방법은 end
에서 $ o (\ sqrt {n}) $ 인 findPrimeOrNot
에서 2
로 반복하는 Math.sqrt(n)
를 사용합니다. $ o (n) o (\ sqrt {n}) $ , $ o (n \ sqrt {n}) $ .
$ o $ 표기법은 알고리즘의 점근 거동에 대해 알려줍니다. 적어도이 경우에는 2 개의 매개 변수가있는 경우 너무 많이 중요하지 않습니다.
그래서 예, 당신의 가정이 완전히 정확합니다 ( $ n $ 대신 end
를 작성한 것을 무시하십시오.
다른 사용자는 올바른 답변이 $ o ((end-start) \ sqrt {end}) $ 이라는 것을 제안했습니다. 나는 이것이 유효한 관점이라고 생각하지만 주어진 경우에 대한 $ o $ 표기법으로
이제 내 질문 : 주어진 알고리즘의 시간 복잡성을 설명하는 공식적으로 올바른 방법은 무엇입니까? 내 추론이 유효하지 않거나 잘못된 잘못입니까?
해결책
모두 "시간 복잡성이 $ o (end \ cdot \ sqrt {end \ cdot \ sqrt {end}) $ "및 "시간 복잡성은 $ o ((start-end) \ cdot \ sqrt {end}) $ "은 올바른 명령문입니다 (관련 정수의 산술 연산이 일정한 시간에 수행 될 수 있음).
두 번째 상한은 경우에 따라 더 가깝습니다.예를 들어, $ start= end-10 $ 을 설정하는 동안 두 번째 상단은 변하지 않지만 두 번째 상단은 $ o (\sqrt {end}) $ .
또한 "IN
다른 팁
$ o (n {1/2}) $ 에서 최악의 경우 $ O (n ^ {1/2})에서 실행됩니다.종종 실행 시간이 더 빠릅니다.예를 들어 NUMBERS N에 대해서는 단일 구분 후에 함수가 반환됩니다.그러나 SQRT (n)까지의 모든 제수가 테스트되는 프레임의 경우 실행 시간은 실제로 $ \ theta (n ^ {1/2}) $ 입니다.그리고 임의의 정수 x가 prime가 in x / log x에 대한 가능성이 있습니다.
평균 부문 수가 정확히 무엇인지 확인해야합니다.알고리즘을 향상시킬 수 있으므로 부서의 수는 적어도 (끝 시작) * sqrt (n) / log n이며 대부분 (끝 시작) * sqrt (n) 부서에서
프레임을 인쇄하려면 인쇄 시간 (끝 - 시작) / log n primes가 프레임을 인쇄하는 시간보다 훨씬 큽니다.합리적인 범위의 프레임.