이 알고리즘의 복잡도는 무엇입니까

이 알고리즘의 시간 복잡도는 얼마나됩니까?이 알고리즘의 복잡도는 무엇입니까

void prime(int n) { 
    int i = 2; 
    while ((n % i) && i <= sqrt(n)) 
     i++; 

    if (i > sqrt(n)) 
     print(“%d is a prime number\n”, n); 
    else 
     print(“%d is not a prime number\n”, n); 
}

출처

2016-09-13 Vincent_Bryan

'n'이 소수이거나 소수가 아니라고 생각하는 이유는 무엇입니까? – Paul

yap, 복잡성이 아무리 크게 변하지 않는다는 것을 알고 있습니다. n은 소수이거나 그렇지 않습니다. 그래서 나는 그것의 복잡성에 대해 잘 모른다. –

그래서 정확히 무엇을 요구하고 있습니까? 귀하의 의견은 귀하의 질문의 첫 번째 라인과 직접적으로 모순됩니다. –

이전에는 잘못 생각했습니다. 안녕하세요 간단히 말해서 O (sqrt (n))입니다 ... 모든 x에 대해 contion이 실행되는 동안보세요 < = n을 나눌 sqrt (n). 그래서 나는 atmost 실행할 수 있습니다 (sqrt (n)) 시간. 그래서 그것은 O (sqrt (n))입니다. 다른 요인은 관련이 없습니다.

출처

2016-09-13 02:55:33 coderredoc

@Vincent_Bryan : 그 earllier처럼 만들기위한 죄송합니다. 지금 내 대답을 확인하십시오. 그것은 sqrt (n)입니다. – coderredoc

O (sqrt (n))가 더 나쁜 경우라고 생각합니다. 평균적인 경우는 무엇입니까? –

복잡도는 약 O (sqrt (N))입니다. 어떤 책들은 이것을 O (N ^0.5)로 표현할 것입니다.

제곱근은 루프의 각 반복을 다시 계산합니다. 이것은 상당히 느린 연산이므로 최적보다 느리지 만 상수 값에 의해서만 계산되므로 계산상의 복잡성에는 영향을 미치지 않습니다.

출처

2016-09-13 04:03:03

이것은 C++ 고정 크기 정수이므로 예. 비록 sqrt가 일정하다면 일정 할 필요는 없지만. 파이썬, 또는 수학 라이브러리에서 큰 정수 유형. –

이 알고리즘의 복잡도는 무엇입니까

답변

관련 문제