범위 내에서 소수 인쇄의 시간 복잡성?

cs.stackexchange https://cs.stackexchange.com/questions/128349

  •  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가 프레임을 인쇄하는 시간보다 훨씬 큽니다.합리적인 범위의 프레임.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top