Kiểm tra nếu thủ lớn-o

Question

chức năng ban đầu của tôi để xác định xem một số là số nguyên tố là:

bool is_prime(int x) { 
    for (int y = 2; y < x; ++y) { 
     if (x % y == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

này chạy với một phức tạp của O(x) như bạn có thể đã phải đi đến x.

Tôi đã học được một số cách tối ưu hóa và cần kiểm tra trên tài khoản lớn của tôi. Đây là chương trình được cải tiến:

bool is_prime(int x) 
{ 
    if (x % 2 == 0 && x > 2) { 
     return false; 
    } 
    for (int y = 3; y*y <= x; y += 2) { 
     if (x % y == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

Liệu thực tế là tôi bây giờ đi lên với sự thay đổi sqrt() này để O(sqrt(x))?

Answer 1

Có, nhưng đây không phải là n s. Độ phức tạp của hàm mới của bạn là O (sqrt (x)). Khi bạn nói O (N) và không chỉ định những gì N, thường được gọi là kích thước của đầu vào. Điều này gây nhầm lẫn cho các hàm lấy một đối số số, vì vậy trong những trường hợp đó, bạn nên rõ ràng.

Answer 2

Tuyệt đối, Sự phức tạp của chức năng mới của bạn là

O (sqrt (x))

Nhưng vẫn còn, có một số chỗ cho tối ưu hóa. Hãy xem mã được đề cập bên dưới:

bool isPrime(int n) 
{ 
    // Boundary cases 
    if (n <= 1) return false; 
    if (n <= 3) return true; 

    // This is checked so that we can skip 
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
     if (n%i == 0 || n%(i+2) == 0) 
      return false; 

    return true; 
}