Thời gian phức tạp của Sieve of Eratosthenes thuật toán

Question

Từ Wikipedia:

Sự phức tạp của thuật toán là O(n(logn)(loglogn)) hoạt động bit.

Làm thế nào để bạn đến nơi đó?

Điều phức tạp bao gồm cụm từ loglogn cho tôi biết rằng có một số sqrt(n) ở đâu đó.

---

Giả sử tôi đang chạy sàng trên 100 số đầu tiên (n = 100), giả định rằng đánh dấu những con số như tổng hợp cần có thời gian liên tục (thực hiện mảng), số lần chúng tôi sử dụng mark_composite() sẽ là một cái gì đó giống như

n/2 + n/3 + n/5 + n/7 + ... + n/97  =  O(n^2)       

Và để tìm ra số nguyên tố tiếp theo (ví dụ để chuyển đến 7 sau khi vượt ra ngoài tất cả những con số mà là bội số của 5), số lượng các hoạt động sẽ là O(n).

Vì vậy, độ phức tạp sẽ là O(n^3). Bạn có đồng ý không?

Answer 1

1. N/2 + n/3 + n/5 +… n/97 không phải là O (n), vì số lượng cụm từ không đổi. [Chỉnh sửa sau khi chỉnh sửa của bạn: O (n) là quá lỏng lẻo một ràng buộc trên.] Một ràng buộc trên lỏng lẻo là n (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1/n) (tổng số nghịch đảo của tất cả các số tối đa n), là O (n log n): xem Harmonic number. Một giới hạn trên thích hợp hơn là n (1/2 + 1/3 + 1/5 + 1/7 +…), đó là tổng các nghịch đảo của số nguyên tố lên đến n, là O (n log log n). (Xem here hoặc here.)

2. Các "tìm ra số nguyên tố tiếp theo" bit là chỉ O (n) tổng thể, amortized - bạn sẽ di chuyển về phía trước để tìm số tiếp theo chỉ n lần trong tổng, không tính theo đầu bậc thang. Vì vậy, toàn bộ phần này của thuật toán chỉ có O (n).

Vì vậy, sử dụng hai giá trị này bạn sẽ nhận được giới hạn trên của hoạt động số học O (n log log n). Nếu bạn đếm các phép toán bit, vì bạn đang xử lý các số lên tới n, chúng có các bit log n, là nơi mà hệ số của log n đi vào, cho phép các hoạt động bit của O (n log n log log n).

Answer 2

Điều phức tạp bao gồm cụm từ loglogn cho tôi biết rằng có một sqrt (n) ở đâu đó.

Hãy nhớ rằng khi bạn tìm số nguyên tố P trong khi sàng, bạn không bắt đầu cắt các số ở vị trí hiện tại của bạn + P; bạn thực sự bắt đầu vượt qua con số tại P^2. Tất cả các bội số của P nhỏ hơn P^2 sẽ bị gạch ngang bởi số nguyên tố trước đó.

Answer 3

1. Các vòng lặp bên trong không n/i bước, nơi i là số nguyên tố => toàn bộ phức tạp là sum(n/i) = n * sum(1/i). Theo số hài hòa chính , số sum (1/i) trong đó i là số nguyên tố là log (log n). Trong tổng số , O(n*log(log n)).

2. Tôi nghĩ rằng vòng lặp trên có thể được tối ưu hóa bằng cách thay thế n với sqrt(n) độ phức tạp thời gian để tổng thể sẽ O(sqrt(n)loglog(n)):

   void isprime(int n) 
   { 
       int prime[n],i,j,count1=0; 
       for(i=0;i<n;i++) 
       { 
        prime[i]=1; 
       } 
       prime[0]=prime[1]=0; 
       for(i=2;i<=n;i++) 
       { 
        if(prime[i]==1) 
        { 
         printf("%d ",i); 
         for(j=2;(i*j)<=n;j++) 
          prime[i*j]=0; 
        } 
       }  
   }