{"id":1021,"date":"2023-02-09T08:52:32","date_gmt":"2023-02-09T00:52:32","guid":{"rendered":"http:\/\/www.algmain.com\/?page_id=1021"},"modified":"2023-02-15T09:26:07","modified_gmt":"2023-02-15T01:26:07","slug":"hash-function","status":"publish","type":"page","link":"http:\/\/www.algmain.com\/index.php\/algorithm-article\/hash-function\/","title":{"rendered":"\u54c8\u5e0c\u51fd\u6570"},"content":{"rendered":"\n

\u6700\u7406\u60f3\u7684\u67e5\u627e\u7b97\u6cd5\u662f\u4e0d\u7ecf\u8fc7\u4efb\u4f55\u6bd4\u8f83\uff0c\u4e00\u6b21\u64cd\u4f5c\u4fbf\u80fd\u5f97\u5230\u6240\u67e5\u7684\u6570\u636e\u8bb0\u5f55\u3002\u90a3\u5c31\u5fc5\u987b\u5728\u6570\u636e\u8bb0\u5f55\u7684\u5b9e\u9645\u4f4d\u7f6e\u548c\u5b83\u7684\u5173\u952e\u5b57\u4e4b\u95f4\u5efa\u7acb\u4e00\u4e2a\u552f\u4e00\u786e\u5b9a\u7684\u5bf9\u5e94\u5173\u7cfb\\(f\\)\uff0c\u4f7f\u6bcf\u4e2a\u5173\u952e\u5b57\u548c\u6570\u636e\u96c6\u5408\u4e2d\u67d0\u4e2a\u552f\u4e00\u7684\u5b9e\u9645\u4f4d\u7f6e\u76f8\u5bf9\u5e94\u3002<\/p>\n\n\n\n

\u5728\u4f9d\u636e\u7ed9\u5b9a\u503c\\(k\\)\u67e5\u627e\u65f6\uff0c\u53ea\u8981\u6839\u636e\u8fd9\u4e2a\u5bf9\u5e94\u5173\u7cfb\\(f\\)\u53ef\u4ee5\u5f97\u5230\u7ed9\u5b9a\u503c\u7684\u50cf\u3002\u82e5\u6570\u636e\u96c6\u5408\u4e2d\u5b58\u5728\u5173\u952e\u5b57\\(key\\)\u548c\u7ed9\u5b9a\u503c\\(k\\)\u76f8\u7b49\u7684\u6570\u636e\u8bb0\u5f55\uff0c\u5219\u6570\u636e\u8bb0\u5f55\u5fc5\u5b9a\u5728\\(f(k)\\) \u6240\u6307\u7684\u5b9e\u9645\u4f4d\u7f6e\u4e0a\u3002\u7531\u6b64\uff0c\u4e0d\u9700\u8981\u8fdb\u884c\u6bd4\u8f83\u4fbf\u53ef\u76f4\u63a5\u53d6\u5f97\u6240\u67e5\u7684\u6570\u636e\u8bb0\u5f55\u3002\u5728\u6b64\u79f0\u8fd9\u4e2a\u5bf9\u5e94\u5173\u7cfb\\(f\\)\u4e3a\u54c8\u5e0c\uff08Hash\uff09\u51fd\u6570\u3002\u54c8\u5e0c\u51fd\u6570\u7684\u5e73\u5747\u67e5\u627e\u957f\u5ea6\u662f1\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662f\\(O(1)\\) \u3002<\/p>\n\n\n\n

\u54c8\u5e0c\u51fd\u6570\u662f\u4e00\u79cd\u8fd0\u7528\u4e8e\u8ba1\u7b97\u673a\u67e5\u627e\u7b97\u6cd5\u7684\u51fd\u6570\uff0c\u662f\u4e00\u4e2a\u5b9e\u9645\u5e94\u7528\u3002\u6240\u6709\u9488\u5bf9\u54c8\u5e0c\u51fd\u6570\u7684\u8ba8\u8bba\uff0c\u5747\u662f\u57fa\u4e8e\u6574\u6570\u8303\u56f4\u5185\u7684\u8ba8\u8bba<\/strong>\u3002\u4e5f\u5373\uff1a\u7ed9\u5b9a\u503c\\(k\\)\u3001\u5173\u952e\u5b57\\(key\\)\u4ee5\u53ca\\(f(k)\\)\u5e94\u5747\u4e3a\u6574\u6570\u6216\u6574\u6570\u5e8f\u5217\u3002\u5982\u679c\u7ed9\u5b9a\u503c\\(k\\)\u3001\u5173\u952e\u5b57\\(key\\)\u6216\u8005\\(f(k)\\)\u4e0d\u4e3a\u6574\u6570\uff08\u4f8b\u5982\uff1a\u6d6e\u70b9\u6570\u3001\u5b57\u7b26\u4e32\u3001\u5b57\u8282\u6570\u7ec4\u7b49\uff09\uff0c\u5747\u53ef\u4ee5\u5728\u8ba1\u7b97\u673a\u4e2d”\u8f6c\u5316”\u4e3a\u9002\u7528\u7684\u6574\u6570\u6216\u8005\u6574\u6570\u5e8f\u5217\u4e88\u4ee5\u8868\u8fbe\u3002<\/p>\n\n\n\n

1 \u5355\u8c03\u54c8\u5e0c\u51fd\u6570<\/h2>\n\n\n\n

\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570\\(f(k)\\)\u4e0e\u7ed9\u5b9a\u503c\\(k\\)\u4e4b\u95f4\u5b58\u5728\u201c\u4e00\u4e00\u6620\u5c04\u201d\u5173\u7cfb\uff0c\u5219\u79f0\u8be5\u51fd\u6570\u4e3a\u201c\u4e00\u4e00\u6620\u5c04\u201d\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

\n

\u5982\u679c\u5728\u67d0\u4e00\u4e2a\u6620\u5c04\u4e0b\uff0c\u5bf9\u4e8e\u96c6\u5408A\u4e2d\u7684\u4e0d\u540c\u5143\u7d20\uff0c\u5728\u96c6\u5408B\u4e2d\u6709\u4e0d\u540c\u7684\u8c61\uff1b\u800c\u4e14B\u4e2d\u7684\u6bcf\u4e00\u5143\u7d20\u5728A\u4e2d\u90fd\u6709\u539f\u8c61\uff0c\u90a3\u4e48\u8fd9\u4e2a\u6620\u5c04\u53eb\u505aA\u5230B\u4e0a\u7684\u201c\u4e00\u4e00\u6620\u5c04\u201d\u3002
\u201c\u4e00\u4e00\u6620\u5c04\u201d\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u6620\u5c04\uff0c\\(f\\)\uff1aA\u2192B\u6ee1\u8db3\u6761\u4ef6\uff1a\u2460A\u4e2d\u4e0d\u540c\u7684\u5143\u7d20\u5bf9\u5e94\u7684\u8c61\u4e0d\u540c\uff1b\u2461B\u6bcf\u4e2a\u5143\u7d20\u90fd\u6709\u539f\u8c61\u3002<\/p>\n<\/blockquote>\n\n\n\n

\u5728\u67d0\u4e2a\u5173\u952e\u5b57\u6570\u503c\u533a\u95f4\u5185\uff0c\u968f\u7740\u5173\u952e\u5b57\u6570\u503c\u7684\u589e\u52a0\uff0c\u54c8\u5e0c\u51fd\u6570\\(f(k)\\)\u5355\u8c03\u9012\u589e\u6216\u8005\u5355\u8c03\u9012\u51cf\uff0c\u5219\u79f0\u8be5\u54c8\u5e0c\u51fd\u6570\u4e3a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u3002\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u90fd\u662f\u201c\u4e00\u4e00\u6620\u5c04\u201d\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

\u4f8b\u5982\uff1a\u54c8\u5e0c\u51fd\u6570\\(f(k)=k\\, mod\\, n\\, ( n\u2208N^\u2217 )\\)\uff0c\u5728\u533a\u95f4\u5185\\([0,\u22121]\\)\u5c31\u662f\u5355\u8c03\u9012\u589e\u51fd\u6570\u3002<\/p>\n\n\n\n

\u5b9a\u4e49\u5982\u4e0b\u54c8\u5e0c\u51fd\u6570\\(sqrt(k)\\)\uff1a\u5bf9\u4e8e\u6240\u6709\u6b63\u6574\u6570\u5173\u952e\u5b57\u8fdb\u884c\u5f00\u65b9\u8fd0\u7b97\uff0c\u53d6\u5c0f\u6570\u70b9\u540e\u4e09\u4f4d\u7684\u6709\u6548\u6570\u5b57\u7ec4\u6210\u65b0\u7684\u6570\u5b57\u3002\u663e\u7136\u8fd9\u4e2a\u54c8\u5e0c\u51fd\u6570\u5728\u533a\u95f4\u5185\\([0,100]\\)\u4e0d\u662f\u5355\u8c03\u51fd\u6570\u3002<\/p>\n\n\n\n

\u7ed9\u5b9a\u503c\\(k\\)<\/th>\u5f00\u65b9\u7ed3\u679c<\/th>\\(sqrt(k)\\)<\/th><\/tr>
0<\/td>0<\/td>0<\/td><\/tr>
1<\/td>1<\/td>0<\/td><\/tr>
2<\/td>1.414<\/td>414<\/td><\/tr>
3<\/td>1.732<\/td>732<\/td><\/tr>
4<\/td>2<\/td>0<\/td><\/tr>
5<\/td>2.236<\/td>236<\/td><\/tr>
6<\/td>2.449<\/td>449<\/td><\/tr>
7<\/td>2.645<\/td>645<\/td><\/tr>
8<\/td>2.828<\/td>828<\/td><\/tr>
9<\/td>3<\/td>0<\/td><\/tr>
10<\/td>3.162<\/td>162<\/td><\/tr>
\u2026\u2026<\/td>\u2026\u2026<\/td>\u2026\u2026<\/td><\/tr>
100<\/td>10<\/td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

2 \u51b2\u7a81<\/h2>\n\n\n\n

\u5728\u54c8\u5e0c\u51fd\u6570\u4e2d\u5bf9\u4e8e\u4e0d\u540c\u6570\u503c\u7684\u5173\u952e\u5b57\u6709\u53ef\u80fd\u5f97\u5230\u540c\u4e00\u5b9e\u9645\u5730\u5740\u503c\uff0c\u5373\\(k_1\u2260k_2\\)\uff0c\u800c\\(f(k_1)=f(k_2)\\)\u3002\u8fd9\u79cd\u73b0\u8c61\u79f0\u505a\u51b2\u7a81\uff08Collision\uff09\u3002<\/p>\n\n\n\n

\u54c8\u5e0c\u51fd\u6570\u662f\u4ece\u5173\u952e\u5b57\u96c6\u5408\u5230\u5b9e\u9645\u5730\u5740\u96c6\u5408\u7684\u6620\u5c04\u3002\u901a\u5e38\u5173\u952e\u5b57\u7684\u96c6\u5408\u6bd4\u8f83\u5927\uff0c\u5305\u62ec\u6240\u6709\u53ef\u80fd\u7684\u5173\u952e\u5b57\u3002\u800c\u5b9e\u9645\u5730\u5740\u96c6\u5408\u7684\u5143\u7d20\u5219\u53d7\u9650\u4e8e\u6240\u5206\u914d\u7684\u7269\u7406\u7a7a\u95f4\u3002<\/p>\n\n\n\n

\u4f8b\u5982\uff1a\u6807\u8bc6\u7b26\u53ef\u5b9a\u4e49\u4e3a\u4ee5\u5b57\u7b26\u4e3a\u9996\u76848\u4f4d\u5b57\u7b26\uff0c\u5219\u4ee5\u6807\u8bc6\u7b26\u4e3a\u5173\u952e\u5b57\u7684\u96c6\u5408\u5927\u5c0f\u4e3a\\(C_{26}^1 \\times C_{36}^7 \\times 7!\u22451.09338\u00d710^{12}\\)\u3002\u5982\u5c06\u5176\u5168\u90e8\u8bb0\u5f55\u5b58\u50a8\uff0c\u5219\u9700\u8981\u7684\u7269\u7406\u5b58\u50a8\u7a7a\u95f4\u5927\u7ea6\u4e3a8.75TB\u3002\u663e\u7136\u8fd9\u4e2a\u6570\u636e\u91cf\u5df2\u7ecf\u8d85\u8fc7\u5e38\u89c4\u8ba1\u7b97\u673a\u5185\u5b58\u6216\u78c1\u76d8\u7684\u5b58\u50a8\u80fd\u529b\u3002<\/p>\n\n\n\n

\u6362\u4e2a\u89d2\u5ea6\u7b80\u5355\u70b9\u8bf4\uff1a\u8bbe\u67094\u4e2a\u5173\u952e\u5b57\u5143\u7d20\uff0c\u90fd\u9700\u8981\u6620\u5c04\u5230\u5b9e\u9645\u5730\u5740\u96c6\u5408\u4e2d\u3002\u5730\u5740\u7f16\u53f7\u4ece1\u52303\u3002\u90a3\u4e48\u5fc5\u7136\u6709\u4e24\u4e2a\u5143\u7d20\u4f1a\u6709\u540c\u4e00\u4e2a\u5b9e\u9645\u5730\u5740\u503c\uff0c\u4e0e\u5177\u4f53\u6240\u9009\u62e9\u7684\u54c8\u5e0c\u51fd\u6570\u65e0\u5173\u3002\u8fd9\u4e2a\u538b\u7f29\u6620\u5c04\u4e5f\u662f”\u62bd\u5c49\u539f\u5219”\u7684\u4f53\u73b0\u3002<\/p>\n\n\n\n

\u603b\u800c\u8a00\u4e4b\uff0c\u54c8\u5e0c\u51fd\u6570\u662f\u4e00\u4e2a\u538b\u7f29\u6620\u50cf\u51fd\u6570\uff0c\u4e0d\u53ef\u907f\u514d\u7684\u8981\u4ea7\u751f\u51b2\u7a81\u3002\u51b2\u7a81\u53ea\u80fd\u5c3d\u53ef\u80fd\u5730\u51cf\u5c11\uff0c\u800c\u4e0d\u80fd\u5b8c\u5168\u907f\u514d\u3002<\/p>\n\n\n\n

3 \u8bc4\u4ef7\u54c8\u5e0c\u51fd\u6570<\/h2>\n\n\n\n

\u540c\u6837\u7684\u5173\u952e\u5b57\u96c6\u5408\u548c\u5b9e\u9645\u5730\u5740\u96c6\u5408\uff0c\u53ef\u4ee5\u6709\u5f88\u591a\u54c8\u5e0c\u51fd\u6570\u53ef\u4f9b\u9009\u62e9\u3002\u672c\u8282\u5c06\u8bb2\u8ff0\u54c8\u5e0c\u51fd\u6570\u7684\u4e3b\u8981\u6027\u8d28\u4ee5\u53ca\u5982\u4f55\u8bc4\u4ef7\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

3.1 \u5206\u8fa8\u80fd\u529b<\/h3>\n\n\n\n

\u5b9a\u4e491\uff1a\u5206\u8fa8\u80fd\u529b<\/strong>\\(D\\)\u662f\u6307\u5173\u952e\u5b57\u96c6\u5408\u7ecf\u54c8\u5e0c\u51fd\u6570\u7684\u6620\u5c04\u540e\uff0c\u6240\u5f97\u50cf\u96c6\u5408\u4e2d\u6240\u6709\u4e0d\u91cd\u590d\u5143\u7d20\u7684\u4e2a\u6570<\/strong>\u3002<\/strong><\/p>\n\n\n\n

\u50cf\u96c6\u5408\u4e2d\u81f3\u5c11\u8981\u6709\u4e00\u4e2a\u5143\u7d20\uff0c\u5373\\(D\u2208N^\u2217\\)\u3002<\/em>\u4f8b\u5982\uff1a\u6240\u6709\u6574\u6570\u5173\u952e\u5b57\u5143\u7d20\u90fd\u9700\u8981\u538b\u7f29\u6620\u5c04\u5230\u7f16\u53f7\u4ece0\u52309999\u7684\u5b9e\u9645\u5730\u5740\u96c6\u5408\u4e2d\u3002\u90a3\u4e48\u8be5\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\\(D=10000\\)\uff1b\u5bf9\u4e8e\u54c8\u5e0c\u51fd\u6570\\(f(k)=C\\)\uff08\u5176\u4e2d\u4e3a\u4efb\u610f\u5e38\u6570\uff09\uff0c\u8be5\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b \\(D=1\\)\uff1b\u5bf9\u4e8e\u54c8\u5e0c\u51fd\u6570\\(f(k)=k\\)\uff0c\u8be5\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\\(D=\u221e\\)\uff1b\u5bf9\u4e8e\u54c8\u5e0c\u51fd\u6570 \\(f(k)=k\\,mod\\,n\\,(n\u2208N^\u2217)\\)\uff0c\u8be5\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\\(D=n\\)\u3002<\/p>\n\n\n\n

\u5206\u8fa8\u80fd\u529b\u7684\u6570\u503c\u8d8a\u5927\uff0c\u8bf4\u660e\u54c8\u5e0c\u51fd\u6570”\u8d8a\u597d”\u3002\u5f53\u5206\u8fa8\u80fd\u529b\\(D=\u221e\\)\u7684\u65f6\u5019\uff0c\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\u6700\u5f3a\uff0c\u540c\u65f6\u50cf\u96c6\u5408\u6240\u4f7f\u7528\u7684\u5b9e\u9645\u7269\u7406\u7a7a\u95f4\u4e5f\u5c06\u662f\u65e0\u7a77\u5927\u3002\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u662f\u4e0d\u53ef\u80fd\u6709\u8db3\u591f\u7684\u8d44\u6e90\u6765\u9884\u5148\u5206\u914d\u51fa\u6240\u6709\u7684\u5b58\u50a8\u7a7a\u95f4\u3002\u56e0\u6b64\u5bf9\u4e8e\u5206\u8fa8\u80fd\u529b\\(D=\u221e\\)\u7684\u54c8\u5e0c\u51fd\u6570\u662f\u6ca1\u6709\u5b9e\u9645\u5e94\u7528\u610f\u4e49\u7684\u3002\u66f4\u591a\u5730\u662f\u9700\u8981\u5728\u5206\u8fa8\u80fd\u529b\u3001\u5b58\u50a8\u7a7a\u95f4\u548c\u65f6\u95f4\u590d\u6742\u5ea6\u4e2d\u5bfb\u627e\u5e73\u8861\u70b9\u3002<\/p>\n\n\n\n

\u6027\u8d282\uff1a\u5bf9\u4e8e\u201c\u4e00\u4e00\u6620\u5c04\u201d\u54c8\u5e0c\u51fd\u6570\uff0c\u4efb\u4f55\u4e24\u4e2a\u95f4\u9694\u4e0d\u8d85\u8fc7\u5176\u5206\u8fa8\u80fd\u529b<\/strong>\\(D\\)\u7684\u5173\u952e\u5b57\u4e0d\u53ef\u80fd\u5177\u6709\u5b8c\u5168\u76f8\u540c\u7684\u538b\u7f29\u6620\u50cf\u6570\u503c\u3002<\/strong><\/p>\n\n\n\n

\u5728\u6574\u6570\u8303\u7574\u5185\uff0c\u5173\u952e\u5b57\\(key\\)\u5177\u6709\u4e00\u5b9a\u7684\u6392\u5217\u89c4\u5f8b\uff0c\u4e14\u8fd9\u79cd\u6392\u5217\u662f\u8fde\u7eed\u7684\u3002\u5f53\u54c8\u5e0c\u51fd\u6570\u662f\u5355\u8c03\u51fd\u6570\u65f6\uff0c\u90a3\u4e48\u4ece\u4efb\u610f\u7ed9\u5b9a\u503c\\(k\\)\u8d77\u59cb\u81f3\\((k+D\u22121)\\)\u8fd9\u4e2a\u8303\u56f4\u5185\uff0c\u8fd9\u6837\\(D\\)\u4e2a\u4e0d\u540c\u7684\u5173\u952e\u5b57\u5c06\u62e5\u6709\\(D\\)\u79cd\u4e0d\u540c\u7684\u538b\u7f29\u6620\u50cf\u6570\u503c\uff08\u5426\u5219\u5c31\u4e0e\u9884\u8bbe\u6761\u4ef6\u77db\u76fe\uff09\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u5bf9\u4e8e\u4efb\u610f\u4e24\u4e2a\u7ed9\u5b9a\u503c\\(k_1\\)\u548c\\(k_2\\)\uff0c\u5982\u679c\u95f4\u9694\u4e0d\u8d85\u8fc7\\(D\\)\uff0c\u5c31\u4e0d\u53ef\u80fd\u83b7\u5f97\u540c\u6837\u7684\u538b\u7f29\u6620\u50cf\u6570\u503c\u3002<\/p>\n\n\n\n

3.2 \u51b2\u7a81\u6982\u7387<\/h3>\n\n\n\n

\u5b9a\u4e493\uff1a\u4e24\u4e2a\u4efb\u610f\u7ed9\u5b9a\u503c<\/strong>\\(k_1\\)\u548c<\/strong>\\(k_2\\)\uff08<\/strong>\\(k_1\u2260k_2\\)\uff09\uff0c\u5bfc\u81f4\u54c8\u5e0c\u51fd\u6570\u51fa\u73b0<\/strong>\\(f(k_1)=f(k_2)\\)\u7684\u6982\u7387\u3002\u8fd9\u4e2a\u6982\u7387\u88ab\u79f0\u4f5c\u51b2\u7a81\u6982\u7387<\/strong>\\(\\lambda\\)\u3002<\/strong><\/p>\n\n\n\n

\u6839\u636e\u5b9a\u4e491\uff0c\u53ef\u77e5\u54c8\u5e0c\u51fd\u6570\u5206\u8fa8\u80fd\u529b\\(D\\)\u610f\u5473\u7740\u538b\u7f29\u6620\u50cf\u96c6\u5408\u4e2d\u6709\\(D\\)\u79cd\u4e0d\u540c\u5143\u7d20\u3002\u968f\u673a\u9009\u62e9\\(N\\)\u4e2a\u4e0d\u540c\u7684\u7ed9\u5b9a\u503c\\(k\\)\uff0c\u7ecf\u8fc7\u54c8\u5e0c\u51fd\u6570\u6620\u5c04\u540e\uff0c\u5f97\u5230\u4e0d\u8d85\u8fc7\\(D\\)\u79cd\u4e0d\u540c\u72b6\u6001\u7684\u8ba1\u6570\u7edf\u8ba1\u7ed3\u679c\uff1a\\(C=\\{c_i| i \\in [1,D]\\}\\) \u3002\u663e\u7136\\(N=\\sum \\limits_{i=1}^D c_i \\)\u3002<\/p>\n\n\n\n

\u67d0\u4e2a\u538b\u7f29\u6620\u50cf\u5143\u7d20\u7684\u51b2\u7a81\u6982\u7387\\(\\lambda_{c_i}\\)\u4e3a\uff1a<\/p>\n\n\n\n

\\[ \\lambda_{c_i} = \\lim_{N \\to \\infty } (\\frac{c_i}{N} \\cdot \\frac {c_i – 1}{N – 1}) \\]<\/p>\n\n\n\n

\u8be5\u54c8\u5e0c\u51fd\u6570\u51b2\u7a81\u6982\u7387\\(\\lambda\\)\u4e3a\uff1a<\/p>\n\n\n\n

\\[ \\lambda = \\sum_{i=1}^{D} \\lambda_{c_i} = \\lim_{N \\to \\infty} \\sum_{i=1}^{D} (\\frac{c_i}{N}\\cdot\\frac{c_i-1}{N})= \\lim_{N \\to \\infty} \\frac{\\sum_\\limits{i=1}^D c_i^2}{N^2} \\]<\/p>\n\n\n\n

\u7531\u6b64\u53ef\u4ee5\u770b\u51fa\uff0c\u5bf9\u4e8e\u4e00\u822c\u54c8\u5e0c\u51fd\u6570\u7684\u51b2\u7a81\u6982\u7387\u8ba1\u7b97\u662f\u6bd4\u8f83\u590d\u6742\u7684\u3002<\/p>\n\n\n\n

\u63a8\u8bba4\uff1a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u7684\u51b2\u7a81\u6982\u7387<\/strong>\\(\\lambda=\\frac {1}{D}\\) \u3002<\/strong><\/p>\n\n\n\n

\u5bf9\u4e8e\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\uff0c\u6bcf\u79cd\u538b\u7f29\u6620\u50cf\u5143\u7d20\u51fa\u73b0\u7684\u6982\u7387\u90fd\u76f8\u7b49\uff0c\u5747\u4e3a\\(\\frac {1}{D}\\) \u3002\u6240\u4ee5\u5bf9\u4e8e\u4efb\u610f\u4e24\u4e2a\u7ed9\u5b9a\u503c\\(k_1\\)\u548c\\(k_2\\)\u3002\u51fa\u73b0\\(f(k_1)\\)\u7684\u6982\u7387\u662f\\(\\frac {1}{D}\\)\uff0c\u51fa\u73b0\\(f(k_2)\\) \u7684\u6982\u7387\u4e5f\u662f\\(\\frac {1}{D}\\)\uff0c\u4e00\u5171\u6709\\(D\\)\u79cd\u72b6\u6001\u3002\u56e0\u6b64\u54c8\u5e0c\u51fd\u6570\u7684\u51b2\u7a81\u6982\u7387\uff08\u5373\\(f(k_1)=f(k_2)\\)\uff09\uff1a<\/p>\n\n\n\n

\\[0\u2264\\lambda=\\frac{1}{D^2}\u22c5D=\\frac {1}{D}\u22641\\]<\/p>\n\n\n\n

\u53ef\u4ee5\u7531\u4e0a\u5f0f\u770b\u51fa\uff1a\u5982\u679c\u4e00\u4e2a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u7684\u50cf\u96c6\u5408\u4e2d\u5143\u7d20\u7684\u4e2a\u6570\u4ec5\u67091\u4e2a\uff0c\u90a3\u4e48\u51b2\u7a81\u6982\u7387\u5c31\u662f100%\uff1b\u5982\u679c\u4e00\u4e2a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u7684\u50cf\u96c6\u5408\u4e2d\u5143\u7d20\u7684\u4e2a\u6570\u662f\u65e0\u7a77\u591a\u4e2a\uff0c\u90a3\u4e48\u51b2\u7a81\u6982\u7387\u5c31\u662f0\u3002<\/p>\n\n\n\n

3.3 \u7b49\u4ef7\u51fd\u6570<\/h3>\n\n\n\n

\u7b49\u4ef7\u51fd\u6570\u662f\u54c8\u5e0c\u51fd\u6570\u4e2d\u4e00\u4e2a\u975e\u5e38\u91cd\u8981\u7684\u6982\u5ff5\u3002<\/p>\n\n\n\n

\u5224\u5b9a5\uff1a\u4e24\u4e2a\u5177\u6709\u76f8\u540c\u5206\u8fa8\u80fd\u529b\u4e14\u6bcf\u79cd\u538b\u7f29\u6620\u50cf\u5143\u7d20\u5747\u5177\u6709\u76f8\u540c\u51b2\u7a81\u6982\u7387\u7684\u54c8\u5e0c\u51fd\u6570\u662f\u7b49\u4ef7\u51fd\u6570\u3002<\/strong><\/p>\n\n\n\n

\u4e25\u683c\u7684\u8bf4\uff1a\u4e24\u79cd\u5b8c\u5168\u4e0d\u540c\u5206\u8fa8\u80fd\u529b\u7684\u54c8\u5e0c\u7b97\u6cd5\u80af\u5b9a\u4e0d\u662f\u7b49\u4ef7\u7b97\u6cd5\u3002\u4f46\u6709\u4e9b\u54c8\u5e0c\u51fd\u6570\u968f\u7740\u5173\u952e\u5b57\u53d6\u503c\u8303\u56f4\u7684\u6269\u5927\uff0c\u5206\u8fa8\u80fd\u529b\u548c\u6bcf\u79cd\u538b\u7f29\u6620\u50cf\u5143\u7d20\u7684\u51b2\u7a81\u6982\u7387\u4f1a\u76f8\u4e92\u63a5\u8fd1\u3002\u8fd9\u4e9b\u54c8\u5e0c\u51fd\u6570\u88ab\u79f0\u4e3a\u6761\u4ef6\u7b49\u4ef7\u51fd\u6570<\/strong>\u3002<\/p>\n\n\n\n

\u63a8\u8bba6\uff1a\u5177\u6709\u76f8\u540c\u5206\u8fa8\u80fd\u529b\u6216\u8005\u51b2\u7a81\u6982\u7387\u7684\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u662f\u7b49\u4ef7\u51fd\u6570\u3002<\/strong><\/p>\n\n\n\n

\u7531\u524d\u9762\u6240\u8ff0\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u7684\u6027\u8d28\uff0c\u4ee5\u53ca\u5224\u5b9a5\u53ef\u4ee5\u5f88\u5bb9\u6613\u8bc1\u660e\u4e0a\u8ff0\u63a8\u8bba\u3002<\/p>\n\n\n\n

\u5982\u4ee5\u4e0b\u6709\u4e24\u4e2a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\uff1a<\/p>\n\n\n\n

    \n
  1. \u51fd\u65701\uff1a\u5c06\u6240\u6709\u6574\u6570\u5173\u952e\u5b57\u5143\u7d20\u538b\u7f29\u6620\u5c04\u5230\u7f16\u53f7\u4ece0\u52309999\u7684\u5b9e\u9645\u5730\u5740\u96c6\u5408\u4e2d\u3002<\/li>\n\n\n\n
  2. \u51fd\u65702\uff1a\u5c06\u6240\u6709\u957f\u5ea6\u4e3a8\u4f4d\u6807\u8bc6\u7b26\uff08\u5b57\u7b26\u4e32\uff09\u5143\u7d20\u7f29\u6620\u5c04\u5230\u7f16\u53f7\u4ece0\u52309999\u7684\u5b9e\u9645\u5730\u5740\u96c6\u5408\u4e2d\u3002<\/li>\n<\/ol>\n\n\n\n

    \u90a3\u4e48\u51fd\u65701\u548c\u51fd\u65702\u7684\u5206\u8fa8\u80fd\u529b\u662f\u76f8\u7b49\u7684\uff08\\(D=10000\\)\uff09\uff0c\u56e0\u6b64\u51fd\u65701\u548c\u51fd\u65702\u662f\u7b49\u4ef7\u51fd\u6570\u3002\u6240\u4ee5\u8bc4\u4ef7\u4e24\u4e2a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u662f\u5426\u7b49\u4ef7\uff0c\u4e3b\u8981\u4e0e\u538b\u7f29\u6620\u5c04\u540e\u7684\u96c6\u5408\u5143\u7d20\u4e2a\u6570\u6709\u5173\u3002<\/p>\n\n\n\n

    \u5bf9\u4e8e\u201c\u4e00\u4e00\u6620\u5c04\u201d\u54c8\u5e0c\u51fd\u6570\uff0c\u53ef\u4ee5\u901a\u8fc7\u4e00\u4e2a\u53d6\u503c\u5bf9\u6362\u8868\uff0c\u5c06\u975e\u5355\u8c03\u201c\u4e00\u4e00\u6620\u5c04\u201d\u54c8\u5e0c\u51fd\u6570\u53d8\u6362\u6210\u4e3a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u3002\u4ec5\u4ece\u8fd9\u4e2a\u89d2\u5ea6\u6765\u770b\uff0c\u4e24\u8005\u662f\u5177\u6709\u7b49\u4ef7\u6027\u7684\u3002\u800c\u5224\u65ad\u4e24\u4e2a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u7684\u7b49\u4ef7\u6027\uff0c\u4ec5\u9700\u8981\u770b\u5206\u8fa8\u80fd\u529b\u662f\u5426\u76f8\u540c\u5373\u53ef\u3002\u8be5\u65b9\u6cd5\u4e00\u6837\u9002\u7528\u4e8e\u201c\u4e00\u4e00\u6620\u5c04\u201d\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

    4 \u54c8\u5e0c\u51fd\u6570\u5206\u7c7b<\/h2>\n\n\n\n

    \u54c8\u5e0c\u51fd\u6570\u53ef\u4ee5\u6309\u7167\u539f\u59cb\u5bf9\u5e94\u5173\u7cfb\\(f\\)\uff0c\u53ef\u4ee5\u5206\u4e3a\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\u548c\u975e\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\u3002\u5176\u4e2d\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\u53c8\u53ef\u4ee5\u5206\u4e3a\uff1a\u5546\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u548c\u4f59\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u3002\u6240\u6709\u7684\u54c8\u5e0c\u51fd\u6570\u5747\u53ef\u4ee5\u901a\u8fc7”\u7b49\u4ef7\u51fd\u6570\u201c\u7684\u6982\u5ff5\uff0c\u7b80\u5316\u548c\u5f52\u7eb3\u6210\u4e3a\uff1a\u5546\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u548c\u4f59\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

    4.1 \u7ebf\u6027\u54c8\u5e0c\u51fd\u6570<\/h3>\n\n\n\n

    \u7ebf\u6027\u7c7b\u54c8\u5e0c\u51fd\u6570\u662f\u6307\u5229\u7528\u6574\u6570\u9664\u6cd5\u4f5c\u4e3a\u5bf9\u5e94\u5173\u7cfb\\(f\\)\u751f\u6210\u65b9\u5f0f\u7684\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

    \u4e3a\u4e86\u65b9\u4fbf\u8ba8\u8bba\uff0c\u5c06\u4e0d\u8d85\u8fc7\u5b9e\u6570\\(x\\)\u7684\u6700\u5927\u6574\u6570\u79f0\u4e3a\\(x\\)\u7684\u6574\u6570\u90e8\u5206\uff0c\u8bb0\u4f5c\u53d6\u6574\u51fd\u6570\\([x]\\) \uff08\u5176\u4e2d\\(x\u2208R\\)\uff09\u3002<\/p>\n\n\n\n

    \u90a3\u4e48\u4e00\u4e2a\u6574\u6570\u6570\u503c\\(k\\)\u53ef\u4ee5\u8868\u8fbe\u4e3a\uff1a\\(k=[\\frac{k}{m}] \\cdot m + n\\)\uff0c\uff08\u5176\u4e2d\\(m \\in N^*\\)\uff0c\\(n \\in N \\)\uff09\u3002<\/p>\n\n\n\n

    \\([\\frac{k}{m}]\\)\u90e8\u5206\u88ab\u6210\u4e3a\u5546\uff0c\\(m\\)\u79f0\u4e3a\u9664\u6570\uff0c\\(n\\)\u6210\u4e3a\u4f59\u6570\uff08\u4e5f\u53ef\u4ee5\u8868\u8fbe\u4e3a\\( n = k\\, mod \\, n\\)\uff09\u3002<\/p>\n\n\n\n

    4.1.1 \u5546\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570<\/h4>\n\n\n\n

    \u7ed9\u5b9a\u4e00\u4e2a\u9664\u6570\u5e8f\u5217\\(M = \\{ m_i | m_i \\in N^* \u4e14 m_i > 1, i \\in N^*\\}\\)\uff0c\u6309\u7167\u5982\u4e0b\u65b9\u5f0f\u5bf9\u6574\u6570\u503c\u6c42\u5f97\u4e00\u4e2a\u7ed3\u679c\u5e8f\u5217\\( R = \\{ r_i | r_i \\in N, i \\in N^* \\}\\)\u3002\u8fd9\u4e2a\u7ed3\u679c\u5e8f\u5217\u7684\u201c\u5012\u5e8f\u201d\\(R^*\\)\u5c31\u662f\u54c8\u5e0c\u51fd\u6570\u7684\u7ed3\u679c\uff1a\\(f_M (k) = R^*\\)\u3002<\/p>\n\n\n\n

    \\[ q_1 = [\\frac{k}{m_1}] \\\\ r_1 = k \\, mod \\, m_1 \\\\
    q_2 = [\\frac{q_1}{m_2}] \\\\ r_2 = q_1 \\, mod \\, m_2 \\\\ \u2026\u2026 \\\\ q_i = [\\frac{q_{i-1}}{m_i}] \\\\ r_i = q_{i-1} \\, mod \\, m_i \\\\ \u2026\u2026 \\\\ \\]<\/p>\n\n\n\n

    \u4f8b\u5982\uff1a\\(k=9527\\)\uff0c\u9664\u6570\u5e8f\u5217\\(M=\\{ 10,10,10,10\\}\\)\u3002\u7ed3\u679c\u5e8f\u5217\u5c31\u662f\\(R=\\{7,5,2,9\\}\\)\uff0c\u5176\u5012\u5e8f\u5c31\u662f\\(R^*=\\{9,5,2,7\\}\\)\u3002<\/p>\n\n\n\n

    \u663e\u7136\u4f9d\u636e\u4e0a\u4f8b\uff0c\u5f53\u9664\u6570\u5e8f\u5217\\(M\\)\u4e2d\u7684\u5143\u7d20\u5747\u4e3a10\u65f6\uff0c\u8fd9\u4e2a\u54c8\u5e0c\u51fd\u6570\u7684\u7ed3\u679c\u5c31\u662f\u6574\u6570\u6570\u503c\\(k\\)\u7684\u5341\u8fdb\u5236\u8ba1\u6570\u7ed3\u679c\u3002<\/p>\n\n\n\n

    \u5f53\u9664\u6570\u5e8f\u5217\\(M\\)\u4e2d\u7684\u5143\u7d20\u4e0d\u5b8c\u5168\u76f8\u540c\u65f6\uff0c\u6b64\u65f6\u54c8\u5e0c\u51fd\u6570\u7684\u7ed3\u679c\u53ef\u4ee5\u79f0\u4e3a\u53d8\u8fdb\u5236\u8ba1\u6570\u7ed3\u679c\u3002\u5728\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u7ed3\u679c\u5e8f\u5217\\(R\\)\u548c\u5176\u5012\u5e8f\\(R^*\\)\u5747\u53ef\u4ee5\u4f5c\u4e3a\u54c8\u5e0c\u51fd\u6570\u7684\u7ed3\u679c\u3002\u5177\u4f53\u4f7f\u7528\u54ea\u4e00\u79cd\uff0c\u53ef\u4ee5\u6839\u636e\u5b9e\u9645\u60c5\u51b5\u5177\u4f53\u5b89\u6392\u3002<\/p>\n\n\n\n

    \u6839\u636e\u54c8\u5e0c\u51fd\u6570\u7684\u7ed3\u679c\u5e8f\u5217\\(R\\)\uff0c\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u6574\u6570\u6570\u503c\\(k^*\\)\uff1a<\/p>\n\n\n\n

    \\[ k^* = (\u2026\u2026(q_i \\times m_i + r_i) \\times m_{i-1} + \u2026\u2026+ r_2) \\times m_1 + r_1 \\quad (q_i = 0,\\, 0 \\le r_i \\le m_i)\\]<\/p>\n\n\n\n

    \u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u9664\u6570\u5e8f\u5217\\(M\\)\u4e0d\u53ef\u80fd\u6709\u65e0\u9650\u591a\u5143\u7d20\uff0c\u56e0\u6b64\u8be5\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\\(D\\)\u5c31\u662f\u6574\u6570\u6570\u503c\\(k^*\\)\u7684\u6570\u503c\u8303\u56f4\u3002<\/p>\n\n\n\n

    \\[D = \\prod\\limits_{i – 1}^n {m_i} = m_1 \\times m_2 \\times m_3 \\times \u2026\u2026 \\times m_n \\]<\/p>\n\n\n\n

    \u53e6\u5916\u53ef\u4ee5\u8bc1\u660e\u5728\u533a\u95f4\\([0,D-1]\\)\u5185\uff0c\u8be5\u54c8\u5e0c\u51fd\u6570\u4e3a\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\uff0c\u5176\u51b2\u7a81\u6982\u7387\u4e3a\\(\\frac{1}{D}\\)\u3002<\/p>\n\n\n\n

    4.1.2 \u4f59\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570<\/h4>\n\n\n\n

    \u7ed9\u5b9a\u4e00\u4e2a\u9664\u6570\u5e8f\u5217\\(M = \\{ m_i | m_i \\in N^* \u4e14 m_i > 1, i \\in N^*\\}\\)\uff0c\u6309\u7167\u5982\u4e0b\u65b9\u5f0f\u5bf9\u6574\u6570\u503c\u6c42\u5f97\u4e00\u4e2a\u7ed3\u679c\u5e8f\u5217\\( R = \\{ r_i | r_i \\in N, i \\in N^* \\}\\)\u3002\u8fd9\u4e2a\u7ed3\u679c\u5e8f\u5217\u5c31\u662f\u54c8\u5e0c\u51fd\u6570\u7684\u7ed3\u679c\uff1a\\(f_M(k)=R\\)\u3002<\/p>\n\n\n\n

    \\[r_1 = k \\, mod \\, m_1 \\\\ r_2 = k \\, mod \\, m_2 \\\\ \u2026\u2026 \\\\ r_i = k \\, mod \\, m_i \\\\ \u2026\u2026\\]<\/p>\n\n\n\n

    \u4f8b\u5982\uff1a\\(k=9527\\)\uff0c\u9664\u6570\u5e8f\u5217\\(M=\\{2,3,5,7,11,13\\} \\)\u3002\u90a3\u4e48\u7ecf\u54c8\u5e0c\u51fd\u6570\u8fd0\u7b97\u53ef\u4ee5\u5f97\u5230\u7ed3\u679c\uff1a\\(R=\\{1,2,2,0,1,11\\}\\)\u3002<\/p>\n\n\n\n

    \u6709\u5173\u4f59\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\\(D\\)\u7684\u8ba1\u7b97\u5c06\u4f1a\u6bd4\u8f83\u590d\u6742\uff0c\u5c06\u653e\u5728\u540e\u9762\u8fdb\u884c\u8ba8\u8bba\u3002\u6b64\u5904\u53ea\u505a\u4e00\u4e2a\u521d\u6b65\u7684\u6982\u5ff5\u4ecb\u7ecd\u3002<\/p>\n\n\n\n

    \u53e6\u5916\u53ef\u4ee5\u8bc1\u660e\u5728\u4efb\u610f\u4e00\u4e2a\u957f\u5ea6\u4e3a\\(D\\)\u7684\u5173\u952e\u5b57\u533a\u95f4\u5185\uff0c\u8be5\u54c8\u5e0c\u51fd\u6570\u4e3a”\u4e00\u4e00\u6620\u5c04”\u54c8\u5e0c\u51fd\u6570\u3002\u7531\u4e8e”\u4e00\u4e00\u6620\u5c04”\u54c8\u5e0c\u51fd\u6570\u4e0e\u5355\u8c03\u54c8\u5e0c\u51fd\u6570\u5177\u6709\u76f8\u540c\u7684\u6027\u8d28\uff0c\u6240\u4ee5\u5176\u51b2\u7a81\u6982\u7387\u4e3a\\(\\frac{1}{D}\\)\u3002<\/p>\n\n\n\n

    4.2 \u975e\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570<\/h3>\n\n\n\n

    \u975e\u7ebf\u6027\u7c7b\u6307\u662f\u54c8\u5e0c\u51fd\u6570\u4e3a\u975e\u7ebf\u6027\u51fd\u6570\u3002\u4e5f\u5c31\u662f\u8bf4\u54c8\u5e0c\u51fd\u6570\u5b8c\u5168\u4f7f\u7528\u975e\u7ebf\u6027\u51fd\u6570\uff0c\u6216\u8005\u975e\u7ebf\u6027\u51fd\u6570\u548c\u7ebf\u6027\u51fd\u6570\u6df7\u5408\u4f7f\u7528\u3002\u53ea\u8981\u54c8\u5e0c\u51fd\u6570\u4f7f\u7528\u4e86\u975e\u7ebf\u6027\u51fd\u6570\uff0c\u90a3\u4e48\u5c31\u88ab\u5212\u5206\u81f3\u975e\u7ebf\u7c7b\u3002<\/p>\n\n\n\n

    \u8fd9\u4e9b\u975e\u7ebf\u6027\u7c7b\u5bf9\u5e94\u5173\u7cfb\u53ef\u4ee5\u5206\u6210\u4e24\u7c7b\uff1a\u975e\u7ebf\u6027\u51fd\u6570\u548c\u5206\u6bb5\u5904\u7406\u65b9\u6cd5\u3002<\/p>\n\n\n\n

    4.2.1 \u975e\u7ebf\u6027\u51fd\u6570<\/h4>\n\n\n\n

    \u5229\u7528\u975e\u7ebf\u6027\u51fd\u6570\u6784\u5efa\u7684\u54c8\u5e0c\u51fd\u6570\u88ab\u79f0\u4e3a\u975e\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\u3002\u8fd9\u4e9b\u51fd\u6570\u4e3b\u8981\u5bfc\u81f4\u6620\u5c04\u540e\u7684\u50cf\u5143\u7d20\u51b2\u7a81\u6982\u7387\u53d1\u751f\u4e0d\u5747\u8861\u6539\u53d8\uff0c\u800c\u5e76\u4e0d\u80fd\u4f7f\u54c8\u5e0c\u51fd\u6570\u5206\u8fa8\u80fd\u529b\u7684\u589e\u52a0\uff08\u751a\u81f3\u662f\u51cf\u5c11\uff09\u3002<\/p>\n\n\n\n

    \u4f8b\u5982\u672c\u6587\u524d\u9762\u6240\u5b9a\u4e49\u7684\u51fd\u6570\\(sqrt(k)\\)\u3002\u6839\u636e\u5176\u63cf\u8ff0\uff0c\u5c31\u53ef\u4ee5\u63a8\u6d4b\u8fd9\u79cd\u54c8\u5e0c\u51fd\u6570\u7684\u5206\u8fa8\u80fd\u529b\\(D \\le 1000\\)\u3002\u56e0\u4e3a\u5bf9\u4e8e\u4efb\u610f\u7ed9\u5b9a\u503c\\(k\u2208[0,999]\\)\uff0c\u5176\u4e2d\u7684\u5b8c\u5168\u5e73\u65b9\u6570\uff0c\u5fc5\u7136\u4f1a\u88ab\u6620\u5c04\u5230\u50cf\u96c6\u5408\u4e2d\u7684\u540c\u4e00\u4e2a\u5143\u7d20\u4e0a\u3002\u8fd9\u79cd\u54c8\u5e0c\u51fd\u6570\u4e0d\u4f1a\u6bd4\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\\(g(k)=k\\, mod \\, 1000\\)\u5177\u6709\u66f4\u5927\u7684\u5206\u8fa8\u80fd\u529b\\(D\\)\u3002\u53e6\u5916\u5728\u8ba1\u7b97\u673a\u4e2d\uff0c\u6574\u6570\u8fd0\u7b97\u66f4\u52a0\u7b80\u5355\u5feb\u6377\uff0c\u6240\u4ee5\u8fd9\u79cd\u975e\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\u662f\u4e0d\u4f1a\u5f97\u5230\u5e7f\u6cdb\u5e94\u7528\u7684\u3002\u5728\u6784\u5efa\u54c8\u5e0c\u7b97\u6cd5\u65f6\u5b8c\u5168\u53ef\u4ee5\u6452\u5f03\u975e\u7ebf\u6027\u54c8\u5e0c\u51fd\u6570\u3002<\/p>\n\n\n\n

    4.2.2 \u5206\u6bb5\u5904\u7406\u65b9\u6cd5<\/h4>\n\n\n\n

    \u5206\u6bb5\u5904\u7406\u65b9\u6cd5\u5c31\u662f\u5c06\u4efb\u610f\u7ed9\u5b9a\u503c\\(k\\)\u5206\u6210\u82e5\u5e72\u90e8\u5206\uff0c\u9488\u5bf9\u6bcf\u4e2a\u90e8\u5206\u5206\u522b\u5efa\u7acb\u4e00\u5b9a\u7684\u5bf9\u5e94\u5173\u7cfb\u3002\u4f8b\u5982\uff1a\u67d0\u4e2a\u624b\u673a\u53f7\u7801\u4e00\u517111\u4f4d\uff0813001071272\uff09\uff0c\u524d\u4e09\u4f4d130\u4ee3\u8868\u4e86\u8fd0\u8425\u5546\uff0c\u540e\u7eed\u4e09\u4f4d0107\u4ee3\u8868\u7684\u5f52\u5c5e\u5730\uff0c1272\u5219\u662f\u7528\u6237\u8bc6\u522b\u7801\u3002\u8fd9\u6837\u53ef\u4ee5\u52a0\u5feb\u67e5\u8be2\u624b\u673a\u7528\u6237\u7684\u6570\u636e\u5b9e\u9645\u5b58\u50a8\u5730\u5740\u3002\u800c\u4e0d\u662f\u5728\u7528\u6237\u6570\u636e\u96c6\u5408\u4e2d\u9010\u4e00\u6bd4\u8f83\u3002<\/p>\n\n\n\n

    \u5047\u8bbe\u4efb\u610f\u7ed9\u5b9a\u503c\\(k\\)\u53ef\u4ee5\u88ab\u5206\u6210\u6bb5\\(n\\)\uff0c\u6bcf\u6bb5\u6240\u6709\u53ef\u80fd\u7684\u72b6\u6001\u4e2a\u6570\u4e3a\\(S_i\\)\uff08\u5176\u4e2d\\(i\u2208[1,n] \uff0cn\u2208N^*\\)\uff09\u3002\u90a3\u4e48\u53ef\u4ee5\u5f97\u51fa\u4ee5\u4e0b\u7ed3\u8bba\uff1a<\/p>\n\n\n\n

    \u4efb\u4f55\u4e00\u4e2a\u6bb5\u7684\u72b6\u6001\u81f3\u5c11\u662f\u6709\u4e24\u4e2a\u72b6\u6001\uff0c\u6216\u8005\u6362\u4e2a\u89d2\u5ea6\u8bf4\u6bcf\u4e00\u4e2a\u6bb5\u90fd\u662f\\(S_i\\)\u8fdb\u5236\u3002\u5f53\u6240\u6709\\(S_i\\)=10 \u65f6\uff0c\u90a3\u4e48\u5176\u5b9e\u5c31\u7b49\u4ef7\u4e8e10\u8fdb\u5236\u8ba1\u6570\uff1b\u5f53\u6240\u6709\\(S_i\\)=2 \u65f6\uff0c\u90a3\u4e48\u5176\u5b9e\u5c31\u7b49\u4ef7\u4e8e2\u8fdb\u5236\u8ba1\u6570\uff1b\u5f53\u6240\u6709\\(S_i\\)=26 \u65f6\uff0c\u90a3\u4e48\u5176\u5b9e\u5c31\u7b49\u4ef7\u4e8e26\u8fdb\u5236\u8ba1\u6570\uff0c\u53ef\u4ee5\u76f8\u5f53\u4e8e\u82f1\u6587\u5355\u8bcd\u5b57\u6bcd\u3002<\/p>\n\n\n\n

    \u4f8b\u5982\uff1a \\(k=9527\\)\uff0c\u5982\u679c\u6309\u716710\u8fdb\u5236\u5206\u6210\u56db\u6bb5\uff0c\u90a3\u4e48\u6bcf\u6bb5\u53ef\u4ee5\u662f9\uff0c5\uff0c2\uff0c7\uff1b\u5982\u679c\u6309\u71672\u8fdb\u5236\u6570\u503c0010 0101 0011 0111\uff0c\u5219\u53ef\u4ee5\u5206\u4e3a16\u6bb5\uff1b\u5982\u679c\u6309\u716716\u8fdb\u5236\u6570\u503c2537\uff0c\u4e5f\u53ef\u4ee5\u5206\u6210\u56db\u6bb5\u3002<\/p>\n\n\n\n

    \u7531\u6b64\u53ef\u4ee5\u53d1\u73b0\u5206\u6bb5\u5bf9\u5e94\u5173\u7cfb\u53ef\u4ee5\u770b\u6210\u662f\u4e00\u79cd\u53d8\u8fdb\u5236\u8ba1\u6570\u65b9\u6cd5\uff0c\u5176\u4e0e\u5546\u6570\u7c7b\u54c8\u5e0c\u51fd\u6570\u4e00\u81f4\uff0c\u5b8c\u5168\u53ef\u4ee5\u5c06\u5176\u5f52\u7eb3\u81f3\u7531\u5546\u6570\u7c7b\u8868\u8fbe\u65b9\u6cd5\u4e2d\u3002<\/p>\n\n\n\n

    4.3 \u6784\u9020\u54c8\u5e0c\u51fd\u6570<\/h3>\n\n\n\n

    \u54c8\u5e0c\u51fd\u6570\u800c\u6784\u5efa\uff0c\u53ef\u4ee5\u662f\u5355\u4e00\u7684\u54c8\u5e0c\u51fd\u6570\uff0c\u4e5f\u53ef\u4ee5\u4f9d\u636e\u591a\u4e2a\u5355\u4e00\u54c8\u5e0c\u51fd\u6570\u7ec4\u5408\u800c\u6210\u3002\u65e0\u8bba\u5982\u4f55\u9009\u62e9\u548c\u6784\u9020\uff0c\u90fd\u5fc5\u987b\u8981\u4fdd\u8bc1\u54c8\u5e0c\u51fd\u6570\u7684\u6700\u7ec8\u5206\u8fa8\u80fd\u529b\\(D\\)\u3002<\/p>\n\n\n\n

    \u9009\u62e9\u4e00\u7ec4\u5bf9\u5e94\u5173\u7cfb\\(f_i\\)\uff08\u5176\u4e2d\\(i\u2208[1,n]\\)\uff0c\\(n\u2208N^*\\)\uff09\uff0c\u901a\u8fc7”\u4e32\u8054”\u6216\u8005”\u5e76\u8054”\u65b9\u5f0f\u6765\u7ec4\u5408\u51fa\u4e00\u79cd\u65b0\u7684\u54c8\u5e0c\u51fd\u6570\uff1a<\/p>\n\n\n\n

    \\[ F_{\u4e32}(k)=f_n(f_{n\u22121}(f_{n\u22122}(\u2026\u2026f_1(k)))) \\]<\/p>\n\n\n\n

    \u6216\u8005<\/p>\n\n\n\n

    \\[F_{\u5e76}(k)={f_1(k),f_2(k),\u2026\u2026f_{n\u22121}(k),f_n(k)}\\]<\/p>\n\n\n\n

    \u663e\u7136\u5bf9\u4e8e\u4e24\u79cd\u7ec4\u5408\u65b9\u5f0f\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u5747\u4e3a\\(O(n)\\)\u3002 \\(F_{\u4e32}(k)\\)\u7684\u603b\u4f53\u5206\u8fa8\u80fd\u529b\u53d6\u51b3\u4e8e\\(f_i\\)\u4e2d\u5206\u8fa8\u80fd\u529b\u7684\u6700\u5c0f\u503c\u3002 \\(F_{\u5e76}(k)\\)\u7684\u603b\u4f53\u5206\u8fa8\u80fd\u529b\u8ba1\u7b97\u8f83\u4e3a\u6bd4\u8f83\u590d\u6742\uff0c\u4f46\u4e0d\u4f4e\u4e8e\\(f_i\\)\u4e2d\u5206\u8fa8\u80fd\u529b\u7684\u6700\u5c0f\u503c\u3002<\/p>\n\n\n\n

    \u56e0\u6b64\u6700\u4f73\u7684\u591a\u5c42\u6b21\u6784\u5efa\u65b9\u5f0f\u53ea\u80fd\u662f”\u5355\u7eaf”\u7684\u5e76\u8054\u65b9\u5f0f\uff0c\u800c\u4e14\u8fd9\u4e9b\u5e76\u8054\u65b9\u5f0f\u5fc5\u987b\u201d\u65e0\u5173\u201c\u3002\u4e0e\u5e76\u8054\u5f62\u5f0f\u76f8\u6bd4\uff0c\u4e32\u8054\u5f62\u5f0f\u662f\u5e94\u5f53\u88ab\u6452\u5f03\u7684\u3002<\/p>\n\n\n\n

    \u5728\u5b9e\u9645\u6784\u5efa\u65f6\uff0c\u8981\u4f7f\u5f97\u603b\u4f53\u5206\u8fa8\u80fd\u529b\u5c3d\u53ef\u80fd\u7684\u5927\uff0c\u5c42\u6b21\u8981\u5c3d\u53ef\u80fd\u5c11\uff08\u4ee5\u51cf\u5c11\u5e73\u5747\u67e5\u627e\u957f\u5ea6\uff09\u3002<\/p>\n\n\n\n

    \n

    AlgMain : \u6574\u6570\u5316<\/a>
    AlgMain :     \u6c42\u539f\u503c<\/a>
    AlgMain :     \u67e5\u627e\u957f\u5ea6<\/a>
    AlgMain :     \u6a21\u62df\u8bc4\u4f30<\/a><\/p>\n\n\n\n

    \u77e5\u4e4e\uff1a\u54c8\u5e0c\u6811\uff08HashTree\uff09\u67e5\u627e\u7b97\u6cd5<\/a>
    CSDN :     \u54c8\u5e0c\u6811\uff08HashTree\uff09\u67e5\u627e\u7b97\u6cd5<\/a><\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"

    \u6700\u7406\u60f3\u7684\u67e5\u627e\u7b97\u6cd5\u662f\u4e0d\u7ecf\u8fc7\u4efb\u4f55\u6bd4\u8f83\uff0c\u4e00\u6b21\u64cd\u4f5c\u4fbf\u80fd\u5f97\u5230\u6240\u67e5\u7684\u6570\u636e\u8bb0\u5f55\u3002\u90a3\u5c31\u5fc5\u987b\u5728\u6570\u636e\u8bb0\u5f55\u7684\u5b9e\u9645\u4f4d\u7f6e\u548c\u5b83\u7684\u5173\u952e\u5b57\u4e4b\u95f4 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":363,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1021","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/1021"}],"collection":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/comments?post=1021"}],"version-history":[{"count":81,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/1021\/revisions"}],"predecessor-version":[{"id":1229,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/1021\/revisions\/1229"}],"up":[{"embeddable":true,"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/pages\/363"}],"wp:attachment":[{"href":"http:\/\/www.algmain.com\/index.php\/wp-json\/wp\/v2\/media?parent=1021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}