Ước lượng giới hạn trên và chứng minh độ phức tạp thời gian trong lý thuyết số OI-6ren

sự chuẩn bị

0,1 biểu tượng tiến bộ

Trên thực tế, nhiều sách giáo khoa toán/giải tích cao cấp đã giới thiệu ký hiệu O lớn và O nhỏ khá chặt chẽ khi giải thích sự so sánh các vô số vi phân. Tuy nhiên, việc lạm dụng ký hiệu của các ký hiệu lịch sử khác nhau [1] đã khiến cho đến nay việc sử dụng chúng trở nên khó khăn. Tác giả đau đầu. Những ký hiệu này tưởng chừng như vô hại nhưng lại có thể trở thành thảm họa nếu không xử lý cẩn thận.

n = O ( n 2 ) ∧ n 2 = O ( n 2 ) ⟹ n = n 2 。

Ví dụ được Knuth đưa ra trong "Toán học cụ thể" [2]. Tính đối xứng ngụ ý bởi " = " làm cho nó không tương thích với g ( x ) = O ( f ( x ) ). được coi là “tập hợp tất cả các hàm số có bậc không lớn hơn f(x)” là cách hiểu chặt chẽ hơn “một hàm số có bậc không lớn hơn f(x)”. Vì vậy, bài viết này sẽ sử dụng f(x) ∈ O. ( g ( x ) ) (đôi khi còn được viết là O ( f ( x ) ) ⊂ O ( g ( x ) ) ) thay vì ký hiệu f ( x ) = O ( g ( x ) ) truyền thống.
n 2 sin n ∈ O ( n 2 ) ⟹ ∑ i = 1 ni 2 sin i ∈ ∑ i = 1 n O ( i 2 ) ⊂ O ( ∑ i = 1 ni 2 ) ⊂ O ( n 3 ) Một số tổng quát hơn , g ( x ) ∈ O ( f ( x ) ) ⟹ ∑ P ( n , i ) g ( i ) ∈ ∑ P ( n , i ) O ( f ( i ) ) ⊂ O ( ∑ P ( n , i ) f ( i ) ).

Bạn không thấy điều đó có gì sai trái phải không? Tác giả cũng mắc lỗi tương tự khi viết bài này. Xin lưu ý rằng đối tượng của ký hiệu O lớn là một hàm f ( i )? Nó chỉ là một giá trị hàm, một số xác định - điều này là do i cũng là một số xác định trong phép liệt kê tổng, chứ không phải n, một ký hiệu thực sự đại diện cho biến. Vậy O ( f ( i ) ) là gì? Không có gì...

Loại lỗi này là không thể tránh khỏi. Chúng ta đã quá quen với việc sử dụng các ký hiệu như x và x 3 + 5 x 2 + x để biểu thị hàm số [1]. nên biểu thị chính hàm đó và f ( x ) chỉ có thể là giá trị hàm. Bằng cách này, chúng ta có thể viết O ( f ) một cách an toàn mà không cần lo lắng về việc nhầm lẫn các biến với các giá trị xác định.

Tuy nhiên, mọi người vẫn thích viết O ( n 2 ) và O ( en 2 ) thay vì viết lạ O ( id 2 ) và O ( exp ∘ id 2 ) . Do đó, có lẽ chúng ta chỉ có thể sử dụng ký hiệu ít chặt chẽ hơn này, Và luôn luôn. nhắc nhở bản thân phải cẩn thận hơn (Ký hiệu "hàm ẩn danh" kiểu lambda ở dạng x ↦ ex 2 có thể tốt hơn?).

Nhưng về kết luận, mệnh đề trên là đúng. Quá trình dẫn xuất đúng phải là ∑ P ( n , i ) g ( i ) ∑ P ( n , i ) C f ( i ) ≤ C ∑ P ( n , i ) f ( i ) ∈ O ( ∑ P ( n , i ) f ( i ) ) .

Bước đầu tiên diễn ra trực tiếp từ định nghĩa của ký hiệu Big O.

Có một bảng chi tiết trong Wikipedia [3] giới thiệu các định nghĩa của các ký hiệu tiệm cận khác nhau. Ngoài ra còn có một lời giải thích rất hay trên OI Wiki [4]. Bạn đọc chưa rành có thể tham khảo. chi tiết có thể tham khảo "Toán học cụ thể" 》Chương 9 [2], Wikipedia và các tài liệu tham khảo (cá nhân tôi đề xuất bài viết ngắn của Knuth về O, Ω, Θ [5]). Bài viết này sử dụng “∈” và “⊂”. Ngoại trừ "thay thế" = ", hệ thống ký hiệu do Knuth đề xuất hoàn toàn được sử dụng.

0,2 số hài hòa $H (N)$ / loạt sóng hài

Tổng riêng H ( n ) của chuỗi hài được định nghĩa là H ( n ) = ∑ i = 1 n 1 i Có thể chứng minh thông qua một số thang đo chuỗi liên quan đến e rằng lim n → ∞ ( H ( n ) − log n ) = c , trong đó c ≈ 0,577 là hằng số Euler. Do đó n H ( n ) ∼ n log n ∈ Θ ( log n ) .

0,3 tổng lũy thừa của các số tự nhiên $P_{P} (N)$ / $P$ - Cấp độ

Chuỗi p có thể được coi là dạng tổng quát của chuỗi hài. Tổng riêng của nó được định nghĩa là P p ( n ) = ∑ i = 1 ni − p .

p - chuỗi có các thuộc tính sau:

Khi p > 1, chuỗi p hội tụ;
Khi p = 1, chuỗi p là chuỗi điều hòa;
Khi −∞ < p < 1, chúng ta chỉ ra rằng P p ( n ) ∼ 1 1 − pn 1 − p ∈ Θ ( n 1 − p ) .

Khi − ∞ < p < 1, ước lượng tiệm cận của chuỗi p - có thể được hiểu từ góc độ tích phân hàm lũy thừa liên tục. Để chứng minh tính chất tiệm cận này, trong trường hợp rời rạc, các hệ số số hạng bậc cao hơn có thể thu được bằng np. tiền tố vi phân + định lý nhị thức, hoặc có thể biểu diễn chính xác bằng lý thuyết giải tích rời rạc (xem phần "Toán học cụ thể" [6]); trong trường hợp liên tục, định lý giá trị trung bình Lagrange nên là một phương pháp ước lượng đơn giản hơn. chúng tôi nhận được: P p ( n ) ∈ { Θ ( n 1 − p ) p < 1 Θ ( n log n ) p = 1 Θ ( 1 ) p > 1 .

1 hàm chia $P_{Với} (N)$

Hàm chia (Divisor Function hay còn gọi là hàm chia và hàm nhân tố) là một loại hàm liên quan đến các thừa số của n. Nó được định nghĩa như sau:

Định nghĩa 1 (hàm số chia) σ z ( n ) = ∑ d ∣ ndz .

Khi z = 0, σ 0 ( n ) được gọi là hàm số ước, thường được viết là d ( n ) hoặc τ ( n ) . Khi z = 1 , σ 1 ( n ) được gọi là tổng của- hàm số chia và thường được viết trực tiếp là σ ( n ).

Ví dụ 1 Ước tính giới hạn tiệm cận trên của σ 0 ( n ).

Nghĩa là, ước tính số thừa số của n. Giới hạn trên nổi tiếng là 2 n, bởi vì tất cả các thừa số d của n nhỏ hơn n tương ứng một với một thừa số khác nd.

Trên thực tế, có thể chứng minh thêm rằng σ 0 ( n ) ∈ o ( n ϵ ) ∀ ϵ > 0 [7], mặc dù điều này không thực tế trong OI.

Ví dụ 2 Ước tính cận trên tiệm cận của σ 0 ^ ( n ) = ∑ i = 1 n σ 0 ( i ).

Nghĩa là, ước tính tổng các thừa số của tất cả các số từ 1 đến n. Đây là một ví dụ ít được biết đến về mặt hình thức nhưng được biết đến nhiều trong ứng dụng của nó. Có thể dễ dàng thu được bằng cách thay đổi thứ tự tính tổng.

σ 0^(n) = ∑ i = 1 n σ 0(i) = ∑ i = 1 n ∑ d ∣ i 1 = ∑ d = 1 n ⌊ nd ⌋ ≤ ∑ d = 1 nnd = n H (n) ∈ O (n log n) 。

Rõ ràng, điều này tốt hơn nhiều so với ước tính tầm thường của O (nn). Ý tưởng của ví dụ này không chỉ là cơ sở lý thuyết của Sàng Eratosthenes (Sàng của Eratosthenes) mà còn là sàng Duchenne, Mobius nhanh. biến đổi và tích chập gcd [8] Xuất hiện ở mọi nơi...

Khai thác thêm thủ thuật này và ước tính chuỗi p, chúng ta có thể có được ước tính tiệm cận của tổng tiền tố của σ z ( n ) ngay cả trước khi xem xét kỹ hơn:

Ví dụ 3 Ước tính cận trên tiệm cận của σ z ^ ( n ) = ∑ i = 1 n σ z ( i ).

σ z ^ ( n ) = ∑ i = 1 n σ z ( i ) = ∑ i = 1 n ∑ d ∣ idz = ∑ d = 1 ndz ⌊ nd ⌋ ≤ n ∑ d = 1 ndz − 1 = n P 1 − z ( n ) ∈ { O ( nz + 1 ) z > 0 O ( n log n ) z = 0 O ( n ) z < 0 。

Thật không may, việc lấy vi phân tổng tiền tố này không đưa ra ước tính chính xác về σ z ( n ).

Bây giờ xin giới thiệu một kỹ thuật chia tỷ lệ quan trọng đã được thử và kiểm tra trong các ước tính tiếp theo.

Mệnh đề 1 ∑ d ∣ nf ( d ) ≤ ∑ i = 1 nf ( ⌊ ni ⌋ ) 。

Rõ ràng, công thức bên phải đếm nhiều số hạng i ∤ n hơn công thức bên trái, vì vậy mệnh đề đúng nhưng chúng ta có thể làm tốt hơn:

Mệnh đề 2 ∑ d ∣ nf ( d ) ≤ ∑ i = 1 nf ( i ) + f ( ⌊ ni ⌋ ) 。

n chia để trị. Trên thực tế, chúng ta đã sử dụng kỹ thuật này trong Ví dụ 1 khi ước lượng σ 0 ( n ).

Ví dụ 4 Ước tính cận trên tiệm cận của σ 1 ( n ).

用 Mệnh đề 1 ： σ 1 ( n ) = ∑ d ∣ nd ≤ ∑ i = 1 n ⌊ ni ⌋ ≤ n H ( n ) ∈ O ( n log n ) 。

Có thể chứng minh rằng sử dụng Dự luật 2 sẽ không mang lại kết quả tốt hơn.

Chúng tôi đã phát hiện ra một sự thật thú vị: giới hạn tiệm cận trên của cả σ 1 ( n ) và σ 0 ^ ( n ) đều là O ( n log n ) .

Ví dụ 5 Ước tính cận trên tiệm cận của σ z ( n ).

Sử dụng Mệnh đề 2 và p - tính chất của chuỗi:

σ z ( n ) = ∑ d ∣ ndz ≤ ∑ i = 1 niz + ⌊ ni ⌋ z ≤ { 2 ∑ i = 1 n ⌊ ni ⌋ z ≤ 2 nz ∑ i = 1 ni − z = 2 nz P z ( n ) z ≥ 0 2 ∑ i = 1 niz = 2 P − z ( n ) z < 0 ∈ { 2 nz O ( 1 ) z > 1 2 n O ( log n ) z = 1 2 nz O ( n 1 − z 2 ) 0 ≤ z < 1 2 O ( n 1 + z 2 ) − 1 < z < 0 2 O ( log n ) z = − 1 2 O ( 1 ) z < − 1 = { O ( nz ) z > 1 O ( n log n ) z = 1 O ( n 1 + z 2 ) − 1 < z < 1 O ( log n ) z = − 1 O ( 1 ) z < − 1 。

Chúng ta có một giới hạn tiệm cận trên khá tốt. Điều đáng chú ý là:

khi $Với = 0$ giờ, $P_{0} (N) \in THE (N^{\frac{1}{2}})$ Điều này phù hợp với kết quả của Ví dụ 1.
khi $Với = \frac{1}{2}$ giờ, $P_{\frac{1}{2}} (N) \in THE (N^{\frac{3}{4}})$ ,Ngay lập tức $\sum_{ngày ∣ N} \sqrt{ngày} \in THE (N^{\frac{3}{4}})$ Câu hỏi mẫu Định lý Luogu P4980 Polya ^{[ 9 ]} Một giải pháp tầm thường hơn để ^{[ 10 ]} Bằng chứng về độ phức tạp về thời gian xuất phát từ điều này. Sau này chúng ta cũng sẽ thấy nó ở khả năng chia hết cho các khối và sàng Dujiao.

Ngoài ra, nếu chỉ sử dụng Mệnh đề 1 thì cận trên tiệm cận của phần − 1 < z < 1 sẽ chỉ được ước tính là O ( n ). Do đó, Mệnh đề 2 ưu việt hơn.

Để biết các giới hạn trên phức tạp hơn và ước tính tiệm cận của các hàm chia, vui lòng tham khảo Wikipedia [7].

2 Chia thành các khối

Còn gọi là phân vùng lý thuyết số. Để tìm ∑ i = 1 nf ( i ) g ( ⌊ ni ⌋ ) ta chia tổng theo d = ⌊ ni ⌋: ∑ dg ( d ) ∑ ⌊ ni ⌋ = df ( i ) Chứng minh rằng với một d xác định, tôi thỏa mãn d = ⌊ ni ⌋ Một khoảng liên tục được lấy, vì vậy nếu tổng tiền tố của f có thể tìm thấy trong O (1), thì số khối # { ⌊ ni ⌋ } i = 1 n là độ phức tạp về thời gian của thuật toán. , ⌊ ni ⌋ có nhiều nhất giá trị ⌊ n ⌋, và khi i ≥ n thì 1 ≤ ⌊ ni ⌋ ≤ n Nó cho thấy rằng nó có nhiều nhất ⌊ n ⌋ giá trị. Do đó, độ phức tạp về thời gian của khối chia hết T 1 ( n ) = # { ⌊ ni ⌋ } i = 1 n 2 n ∈ O ( n ) .

Để thuận tiện, trong văn bản sau D ( n ) = { ⌊ ni ⌋ } i = 1 n .

2.1 Chia khối lồng nhau

Củng cố Dự Luật 2, chúng ta có tỷ lệ chung sau:

Mệnh đề 3 ∑ d ∣ nf ( d ) ≤ ∑ d ∈ D ( n ) f ( d ) ≤ ∑ i = 1 nf ( i ) + f ( ⌊ ni ⌋ ) 。

Chìa khóa để thiết lập LHS là { d : d ∣ n } ⊂ D ( n ); và bản chất của RHS là ước tính nêu trên về giới hạn trên của số khối có thể chia được.

Lưu ý rằng Mệnh đề 2 là cốt lõi của chứng minh ở Ví dụ 5, và Mệnh đề 3 là phiên bản nâng cao của Mệnh đề 2, vì vậy chúng ta có một bản sao chứng minh của Ví dụ 5.

Ví dụ 6 Cho S z ( n ) = ∑ d ∈ D ( n ) dz Khi đó giới hạn trên và cận trên tiệm cận của σ z ( n ) trong Ví dụ 5 cũng áp dụng cho S z ( n ).

Hiện tại có thể ước tính độ phức tạp về thời gian T 2 của các khối chia được lồng nhau ∑ i = 1 nf ( i ) ∑ j = 1 ⌊ ni ⌋ g ( j ) h ( ⌊ nij ⌋ Lấy z = cho Ví dụ 6 1 ). 2 , ngay lập tức T 2 ( n ) = ∑ d ∈ D ( n ) T 1 ( d ) ≤ 2 ∑ d ∈ D ( n ) d = 2 S 1 2 ( n ) 4 n P 1 2 ( n ) ∈ O ( n 3 4 ) .

Ta có thể khái quát hóa thêm. Giả sử ∀ m ≥ 0 , ∃ zm : 0 ≤ zm < 1 , T m ( n ) = O ( nzm ) , ta có.

T m + 1 ( n ) = ∑ d ∈ D ( n ) T m ( d ) ≤ C ∑ d ∈ D ( n ) nzm = CS zm ( n ) ∈ O ( n 1 + zm 2 ) 。

Do đó zm + 1 = 1 + zm 2 . Điều kiện biên z 0 = 0 , đệ quy chuỗi thu được zm = 1 − 2 − m , và phép kiểm tra thỏa mãn điều kiện. Do đó, độ phức tạp về thời gian của m khối chia số nguyên lồng nhau là T. m ( n ) ∈ O ( n 1 − 2 − m ) .

3 Du Jiaosie

Du Jiaosieve có thể giải tổng tiền tố của một số hàm lý thuyết số với độ phức tạp thời gian tuyến tính nhỏ hơn. Giả sử f là một hàm lý thuyết số và chúng tôi hy vọng sẽ nhanh chóng tìm thấy tổng tiền tố của nó f ^ ( n ) = ∑ i. = 1 nf ( i ) . Xét hàm lý thuyết số g và h = g ∗ f , h ( n ) = ∑ d ∣ ng ( d ) f ( nd ) và tiền tố cả hai đầu để có h ^ ( n ) = ∑ i = 1 nh ( i ) = ∑ i = 1 n ∑ d ∣ ig ( d ) f ( id ) = ∑ d = 1 ng ( d ) ∑ i = 1 ⌊ nd ⌋ f ( i ) = ∑ d = 1 ng ( d ) f ^ ( ⌊ nd ⌋ ) = g ( 1 ) f ^ ( n ) + ∑ d = 2 ng ( d ) f ^ ( ⌊ nd ⌋ ) Do đó f ^ ( n ) = 1 g ( 1 ) ( h ^ ( n ) − ∑ d = 2 ng ( d ) f ^ ( ⌊ nd ⌋ ) ) .

Do đó, nếu tính tổng tiền tố của g và h trong O(1) thì tổng tiền tố của f có thể tính đệ quy bằng cách chia thành các khối theo công thức trên.

Độ phức tạp của thuật toán được phân tích dưới đây. Lưu ý rằng ⌊ ⌊ ni ⌋ j ⌋ = ⌊ nij ⌋, do đó các biến độc lập liên quan đến đệ quy một vòng có thể được biểu thị dưới dạng d = ⌊ ni ⌋. d ) được chia thành các khối Phải mất T 1 ( d ). Nếu sử dụng đệ quy ghi nhớ, theo phân tích ở phần trước, tổng độ phức tạp về thời gian của thuật toán là ∑ d ∈ D ( n ) T 1 ( d ) = T 2 ( n ) ∈ O ( n 3 4 ) .

Nhưng chúng ta có thể làm tốt hơn - xem xét sàng lọc tuyến tính K f(n) đầu tiên với độ phức tạp thời gian là O(K) và tìm tổng tiền tố. Khi đó, khi giải đệ quy, f^(d) với d ≤ K là Không cần thiết. tái diễn xuống dưới nữa. Để phân tích loại độ phức tạp về thời gian này, hãy mở rộng cuối cùng cho Dự luật 3:

Mệnh đề 4 ∑ d ∣ nd > K f ( d ) ≤ ∑ d ∈ D ( n ) d > K f ( d ) ≤ ∑ K < i ≤ nf ( i ) + ∑ 1 ≤ i ≤ min { ⌊ n K ⌋ , n } f ( ⌊ ni ⌋ ) 。

Đặc biệt khi K > n thì có.

∑ d ∣ nd > K f ( d ) ≤ ∑ d ∈ D ( n ) d > K f ( d ) ≤ ∑ 1 ≤ i ≤ ⌊ n K ⌋ f ( ⌊ ni ⌋ ) 。

Do đó, bằng cách sử dụng Mệnh đề 4, khi K > n, độ phức tạp về thời gian của thuật toán trong phần đệ quy giảm xuống.

∑ d ∈ D ( n ) d > KT 1 ( d ) = ∑ 1 ≤ i ≤ ⌊ n K ⌋ T 1 ( ⌊ ni ⌋ ) ≤ ∑ 1 ≤ i ≤ ⌊ n K ⌋ C ni = C n ∑ 1 ≤ i ⌊ n K ⌋ i − 1 2 = C n P 1 2 ( ⌊ n K ⌋ ) ∈ n O ( ( n K ) 1 2 ) ⊂ O ( n K − 1 2 ) 。

Tổng độ phức tạp về thời gian là O ( K ) + O ( n K − 1 2 ) .

Để giảm thiểu độ phức tạp thời gian, lấy K = n 2 3 và đạt được độ phức tạp thời gian tối ưu O (n 2 3).

Việc chứng minh độ phức tạp thời gian của phần này chủ yếu đề cập đến bài viết [11].

Tài liệu tham khảo

1. Lạm dụng ký hiệu - wikipedia . (nd). https://en.wikipedia.org/wiki/Lạm_dụng_ký_hiệu#Ký_hiệu_chức_năng .

2. Graham, RL, Knuth, DE, & Patashnik, O. (1994). Toán học cụ thể: Nền tảng cho khoa học máy tính (thứ hai, trang 443–449). Addison-Wesley.

3. Ký hiệu big o - wikipedia # họ ký hiệu bachmann–landau . (nd). https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations .

4. Độ phức tạp - OI wiki . (thứ hai). https://oi-wiki.org/basic/complexity/#%E6%B8%90%E8%BF%9B%E7%AC%A6%E5%8F%B7%E7%9A%84%E5%AE%9A%E4%B9%89 .

5. Knuth, DE (1976). Omicron lớn, omega lớn và theta lớn. Tin tức SIGACT , 8 (2), 18–24. https://doi.org/10.1145/1008328.1008329

6. Graham, RL, Knuth, DE, & Patashnik, O. (1994). Toán học cụ thể: Nền tảng cho khoa học máy tính (thứ hai, trang 47–56). Addison-Wesley.

7. Hàm chia - wikipedia # growth_rate . (nd). https://en.wikipedia.org/wiki/Divisor_function#Growth_rate .

8. sun123zxy. (2020). blog của sun123zxy - Vấn đề và giải pháp tích chập GCD theo chủ đề OI gốc . https://blog.sun123zxy.top/posts/20201206-gcdconv/ .

9. P4980 [Mẫu] định lý pólya - Luogu | Hệ sinh thái mới của giáo dục khoa học máy tính . (thứ). https://www.luogu.com.cn/problem/P4980 .

10. sun123zxy. (2020). blog của sun123zxy - Đếm các lớp tương đương: Định lý Bổ đề & Polya của Burnside . http://blog.sun123zxy.top/posts/20200321-burnside/#s-4.3 .

11. Những người khác. (2022). Du Jiaosie . https://zhuanlan.zhihu.com/p/521699400 .

Cuối cùng, bài viết này về ước lượng giới hạn trên và bằng chứng về độ phức tạp thời gian trong lý thuyết số OI kết thúc tại đây. Nếu bạn muốn biết thêm về ước tính giới hạn trên và bằng chứng về độ phức tạp thời gian trong lý thuyết số OI, vui lòng tìm kiếm bài viết CFSDN. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .

trang đầu

đã học

6Ren AI

Trung tâm mua sắm