{"id":59370,"date":"2026-01-13T19:17:09","date_gmt":"2026-01-13T11:17:09","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/59370.html"},"modified":"2026-01-13T19:17:09","modified_gmt":"2026-01-13T11:17:09","slug":"%e8%ae%ba%e6%96%87%e5%88%86%e4%ba%ab%e4%b8%8e%e8%a7%a3%e6%9e%90%ef%bd%9c%e9%80%bc%e8%bf%91%e6%9e%81%e9%99%90%ef%bc%9a%e5%8d%95%e9%81%8d%e6%b5%81%e5%bc%8f%e7%ae%97%e6%b3%95%e4%b8%ad%e6%9c%80%e5%a4%a7","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/59370.html","title":{"rendered":"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834"},"content":{"rendered":"<p>\u5728\u5f53\u4eca\u5927\u6570\u636e\u65f6\u4ee3&#xff0c;\u6570\u636e\u5e38\u4ee5\u9ad8\u901f\u201c\u6d41\u201d\u7684\u5f62\u5f0f\u6c79\u6d8c\u800c\u81f3&#xff0c;\u65e0\u6cd5\u88ab\u5b8c\u6574\u5b58\u50a8\u3002\u6d41\u5f0f\u7b97\u6cd5&#xff08;Streaming Algorithm&#xff09;\u5e94\u8fd0\u800c\u751f&#xff0c;\u5b83\u8981\u6c42\u4ec5\u7528\u5355\u904d\u6216\u5c11\u6570\u51e0\u904d\u626b\u63cf\u6570\u636e&#xff0c;\u4e14\u4f7f\u7528\u8fdc\u5c0f\u4e8e\u6570\u636e\u603b\u91cf\u7684\u5185\u5b58&#xff08;\u5373\u6b21\u7ebf\u6027\u7a7a\u95f4&#xff09;\u6765\u5b8c\u6210\u8ba1\u7b97\u4efb\u52a1\u3002\u8fd9\u79cd\u6a21\u578b\u5bf9\u4e8e\u5904\u7406\u8d85\u5927\u89c4\u6a21\u56fe\u6570\u636e\u5c24\u4e3a\u91cd\u8981\u3002\u5176\u4e2d&#xff0c;\u6700\u5927\u6709\u5411\u5272&#xff08;Maximum Directed Cut&#xff0c; MaxDiCut&#xff09;\u4f5c\u4e3a\u4e00\u4e2a\u57fa\u7840\u6027\u7684\u7ea6\u675f\u6ee1\u8db3\u95ee\u9898&#xff0c;\u4e0d\u4ec5\u662f\u56fe\u8bba\u7684\u6838\u5fc3&#xff0c;\u66f4\u662f\u6d4b\u8bd5\u6d41\u5f0f\u7b97\u6cd5\u8bbe\u8ba1\u80fd\u529b\u7684\u201c\u8bd5\u91d1\u77f3\u201d\u3002\u957f\u671f\u4ee5\u6765&#xff0c;\u4e00\u4e2a\u6839\u672c\u6027\u95ee\u9898\u60ac\u800c\u672a\u51b3&#xff1a;\u5728\u5355\u904d\u6d41\u5f0f\u4e14\u4ec5\u4f7f\u7528\u6b21\u7ebf\u6027\u7a7a\u95f4\u7684\u9650\u5236\u4e0b&#xff0c;MaxDiCut\u80fd\u8fbe\u5230\u7684\u6700\u4f73\u8fd1\u4f3c\u6bd4\u662f\u591a\u5c11&#xff1f;<\/p>\n<p>2025\u5e74&#xff0c;\u6765\u81ea\u4e1c\u5317\u5927\u5b66\u7684Amir Azarmehr\u3001Soheil Behnezhad\u3001Shane Ferrante\u548cMohammad Saneian\u5408\u4f5c\u5b8c\u6210\u4e86\u4e00\u9879\u91cc\u7a0b\u7891\u5f0f\u7684\u5de5\u4f5c&#xff0c;\u7ed9\u51fa\u4e86\u8fd9\u4e2a\u95ee\u9898\u7684\u6700\u7ec8\u7b54\u6848&#xff1a;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         (<\/p>\n<p>          1<\/p>\n<p>          2<\/p>\n<p>         \u2212<\/p>\n<p>         \u03b5<\/p>\n<p>         )<\/p>\n<p>        (\\\\frac{1}{2} &#8211; \\\\varepsilon)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.1901em;vertical-align: -0.345em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mopen nulldelimiter\"><\/span><span class=\"mfrac\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8451em\"><span class=\"\" style=\"top: -2.655em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><span class=\"\" style=\"top: -3.23em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"frac-line\" style=\"border-bottom-width: 0.04em\"><\/span><\/span><span class=\"\" style=\"top: -3.394em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.345em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><span class=\"mclose nulldelimiter\"><\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c; \u4e14\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          n<\/p>\n<p>           1<\/p>\n<p>           \u2212<\/p>\n<p>            \u03a9<\/p>\n<p>            \u03b5<\/p>\n<p>           (<\/p>\n<p>           1<\/p>\n<p>           )<\/p>\n<p>        n^{1-\\\\Omega_{\\\\varepsilon}(1)}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.888em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.888em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">\u03a9<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1645em\"><span class=\"\" style=\"top: -2.357em;margin-left: 0em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">\u03b5<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.143em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mtight\">1<\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002 \u4ed6\u4eec\u7684\u8bba\u6587\u300aHalf-Approximating Maximum Dicut in the Streaming Setting\u300b\u6b63\u5f0f\u786e\u7acb\u4e86<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        1<\/p>\n<p>        \/<\/p>\n<p>        2<\/p>\n<p>       1\/2<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/2<\/span><\/span><\/span><\/span><\/span>\u5c31\u662f\u8be5\u95ee\u9898\u7684\u6d41\u5f0f\u8fd1\u4f3c\u8ba1\u7b97\u6781\u9650\u3002\u672c\u6587\u5c06\u6df1\u5165\u5256\u6790\u8fd9\u9879\u5de5\u4f5c\u7684\u80cc\u666f\u3001\u6311\u6218\u3001\u6838\u5fc3\u601d\u60f3\u4e0e\u6280\u672f\u4eae\u70b9&#xff0c;\u5e26\u9886\u8bfb\u8005\u9886\u7565\u5176\u7cbe\u5999\u4e4b\u5904\u3002<\/p>\n<h3>\u4e00\u3001 \u95ee\u9898\u80cc\u666f\u4e0e\u5386\u53f2\u8109\u7edc<\/h3>\n<h4>1. \u4ec0\u4e48\u662fMaxDiCut&#xff1f;<\/h4>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6709\u5411\u56fe <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        G<\/p>\n<p>        &#061;<\/p>\n<p>        (<\/p>\n<p>        V<\/p>\n<p>        ,<\/p>\n<p>        E<\/p>\n<p>        )<\/p>\n<p>       G&#061;(V, E)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\">G<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">&#061;<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.2222em\">V<\/span><span class=\"mpunct\">,<\/span><span class=\"mspace\" style=\"margin-right: 0.1667em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0576em\">E<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c; MaxDiCut\u7684\u76ee\u6807\u662f\u5c06\u9876\u70b9\u96c6 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        V<\/p>\n<p>       V<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.2222em\">V<\/span><\/span><\/span><\/span><\/span> \u5212\u5206\u4e3a\u4e24\u4e2a\u5b50\u96c6 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        (<\/p>\n<p>        S<\/p>\n<p>        ,<\/p>\n<p>        V<\/p>\n<p>        \u2216<\/p>\n<p>        S<\/p>\n<p>        )<\/p>\n<p>       (S, V\\\\setminus S)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0576em\">S<\/span><span class=\"mpunct\">,<\/span><span class=\"mspace\" style=\"margin-right: 0.1667em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.2222em\">V<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2216<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0576em\">S<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c; \u4f7f\u5f97\u4ece <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        S<\/p>\n<p>       S<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0576em\">S<\/span><\/span><\/span><\/span><\/span> \u6307\u5411 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        V<\/p>\n<p>        \u2216<\/p>\n<p>        S<\/p>\n<p>       V\\\\setminus S<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.2222em\">V<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2216<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0576em\">S<\/span><\/span><\/span><\/span><\/span> \u7684\u6709\u5411\u8fb9\u6570\u91cf\u6700\u5927\u5316\u3002\u8fd9\u662f\u4e00\u4e2a\u7ecf\u5178\u7684NP\u96be\u4f18\u5316\u95ee\u9898\u3002<\/p>\n<h4>2. \u6d41\u5f0f\u8ba1\u7b97\u6a21\u578b\u4e0e\u6311\u6218<\/h4>\n<p>\u5728\u6d41\u5f0f\u6a21\u578b\u4e2d&#xff0c;\u56fe\u7684\u8fb9\u4ee5\u4efb\u610f\u987a\u5e8f\u4e00\u6761\u6761\u5230\u8fbe&#xff0c;\u7b97\u6cd5\u53ea\u80fd\u987a\u5e8f\u8bfb\u53d6\u4e00\u6b21&#xff08;\u5355\u904d&#xff09;&#xff0c;\u4e14\u53ea\u80fd\u4f7f\u7528 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        o<\/p>\n<p>        (<\/p>\n<p>         n<\/p>\n<p>         2<\/p>\n<p>        )<\/p>\n<p>       o(n^2)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0641em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">o<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u751a\u81f3 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        o<\/p>\n<p>        (<\/p>\n<p>        n<\/p>\n<p>        )<\/p>\n<p>       o(n)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">o<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">n<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u7684\u5185\u5b58&#xff08;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        n<\/p>\n<p>       n<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">n<\/span><\/span><\/span><\/span><\/span>\u4e3a\u9876\u70b9\u6570&#xff09;\u3002\u5bf9\u4e8eMaxDiCut&#xff0c;\u4e00\u4e2a\u5e73\u51e1\u7684\u7b97\u6cd5\u662f\u5b58\u50a8 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        O<\/p>\n<p>        (<\/p>\n<p>        n<\/p>\n<p>        )<\/p>\n<p>       O(n)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">n<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u6761\u8fb9&#xff0c;\u5229\u7528\u52a0\u6027\u5272\u7a00\u758f\u5668&#xff08;additive cut sparsifier&#xff09;\u5373\u53ef\u83b7\u5f97<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        (<\/p>\n<p>        1<\/p>\n<p>        \u2212<\/p>\n<p>        \u03b5<\/p>\n<p>        )<\/p>\n<p>       (1-\\\\varepsilon)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\">1<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u8fd1\u4f3c\u3002\u56e0\u6b64&#xff0c;\u7814\u7a76\u7684\u7126\u70b9\u81ea\u7136\u8f6c\u5411\u4e86\u771f\u6b63\u6b21\u7ebf\u6027\u7a7a\u95f4&#xff08;\u5373 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         n<\/p>\n<p>          1<\/p>\n<p>          \u2212<\/p>\n<p>          \u03a9<\/p>\n<p>          (<\/p>\n<p>          1<\/p>\n<p>          )<\/p>\n<p>       n^{1-\\\\Omega(1)}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.888em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.888em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mtight\">\u03a9<\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mtight\">1<\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7a7a\u95f4&#xff09;\u4e0b\u80fd\u83b7\u5f97\u7684\u6700\u4f73\u8fd1\u4f3c\u6bd4\u3002<\/p>\n<h4>3. \u7814\u7a76\u8fdb\u5c55\u4e0e\u74f6\u9888<\/h4>\n<ul>\n<li>\u4e0b\u754c\u5960\u57fa&#xff1a;Kapralov\u548cKrachun\u5728STOC\u201820\u7684\u6770\u51fa\u5de5\u4f5c\u8bc1\u660e&#xff0c;\u4efb\u4f55\u4f7f\u7528<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          n<\/p>\n<p>           1<\/p>\n<p>           \u2212<\/p>\n<p>           \u03a9<\/p>\n<p>           (<\/p>\n<p>           1<\/p>\n<p>           )<\/p>\n<p>        n^{1-\\\\Omega(1)}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.888em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.888em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mtight\">\u03a9<\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mtight\">1<\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u7a7a\u95f4\u7684\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5&#xff0c;\u5176MaxDiCut\u8fd1\u4f3c\u6bd4\u4e0d\u53ef\u80fd\u8d85\u8fc7<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         1<\/p>\n<p>         \/<\/p>\n<p>         2<\/p>\n<p>        1\/2<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/2<\/span><\/span><\/span><\/span><\/span>\u3002\u8fd9\u4e3a\u6240\u6709\u540e\u7eed\u52aa\u529b\u8bbe\u5b9a\u4e86\u5929\u82b1\u677f\u3002<\/li>\n<li>\u4e0a\u754c\u8ffd\u8d76&#xff1a;\n<ul>\n<li>\u65e9\u671f\u5de5\u4f5c&#xff08;\u5982Guruswami\u7b49\u4eba&#xff09;\u5728<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           O<\/p>\n<p>           (<\/p>\n<p>           log<\/p>\n<p>           \u2061<\/p>\n<p>           n<\/p>\n<p>           )<\/p>\n<p>          O(\\\\log n)<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mop\">lo<span style=\"margin-right: 0.0139em\">g<\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.1667em\"><\/span><span class=\"mord mathnormal\">n<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u7a7a\u95f4\u4e0b\u8fbe\u5230\u4e86\u8fd1<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>           2<\/p>\n<p>           \/<\/p>\n<p>           5<\/p>\n<p>          2\/5<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">2\/5<\/span><\/span><\/span><\/span><\/span>\u7684\u8fd1\u4f3c\u6bd4\u3002<\/li>\n<li>Chou, Golovnev, Sudan\u5c06\u5176\u63d0\u5347\u81f3<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           4<\/p>\n<p>           \/<\/p>\n<p>           9<\/p>\n<p>          4\/9<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">4\/9<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5e76\u8bc1\u660e\u4e86\u8d85\u8d8a\u6b64\u754c\u9650\u9700\u8981<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>           \u03a9<\/p>\n<p>           (<\/p>\n<p>            n<\/p>\n<p>           )<\/p>\n<p>          \\\\Omega(\\\\sqrt{n})<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0503em;vertical-align: -0.25em\"><\/span><span class=\"mord\">\u03a9<\/span><span class=\"mopen\">(<\/span><span class=\"mord sqrt\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8003em\"><span class=\"svg-align\" style=\"top: -3em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"mord\" style=\"padding-left: 0.833em\"><span class=\"mord mathnormal\">n<\/span><\/span><\/span><span class=\"\" style=\"top: -2.7603em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"hide-tail\" style=\"min-width: 0.853em;height: 1.08em\"><\/p>\n<p>              <\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.2397em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u7a7a\u95f4\u3002<\/li>\n<li>\u7ecf\u8fc7\u4e00\u7cfb\u5217\u6539\u8fdb&#xff0c;Saxena, Singer, Sudan, Velusamy\u5728FOCS\u201823\/SODA\u201825\u7684\u5de5\u4f5c\u5c06\u4e00\u822c\u56fe\u7684\u8fd1\u4f3c\u6bd4\u63a8\u81f30.485&#xff0c;\u4f7f\u7528\u4e86<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           O<\/p>\n<p>           (<\/p>\n<p>            n<\/p>\n<p>           )<\/p>\n<p>          O(\\\\sqrt{n})<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0503em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord sqrt\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8003em\"><span class=\"svg-align\" style=\"top: -3em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"mord\" style=\"padding-left: 0.833em\"><span class=\"mord mathnormal\">n<\/span><\/span><\/span><span class=\"\" style=\"top: -2.7603em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"hide-tail\" style=\"min-width: 0.853em;height: 1.08em\"><\/p>\n<p>              <\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.2397em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u7a7a\u95f4\u3002<\/li>\n<li>\u7136\u800c&#xff0c;\u8ddd\u79bb<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           1<\/p>\n<p>           \/<\/p>\n<p>           2<\/p>\n<p>          1\/2<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/2<\/span><\/span><\/span><\/span><\/span>\u7684\u4e0b\u754c\u4ecd\u6709\u5fae\u5c0f\u4f46\u5173\u952e\u7684\u5dee\u8ddd\u3002Saxena\u7b49\u4eba\u5728SODA\u201825\u7684\u53e6\u4e00\u7bc7\u5de5\u4f5c\u4e2d&#xff0c;\u5728\u5047\u8bbe\u56fe\u662f\u5e38\u6570\u5ea6&#xff08;constant-degree&#xff09;\u7684\u524d\u63d0\u4e0b&#xff0c;\u9996\u6b21\u5b9e\u73b0\u4e86<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>           (<\/p>\n<p>           1<\/p>\n<p>           \/<\/p>\n<p>           2<\/p>\n<p>           \u2212<\/p>\n<p>           \u03b5<\/p>\n<p>           )<\/p>\n<p>          (1\/2-\\\\varepsilon)<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\">1\/2<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u8fd1\u4f3c\u3002\u4f46\u5bf9\u4e8e\u9876\u70b9\u5ea6\u6570\u53ef\u80fd\u5f88\u9ad8\u7684\u4e00\u822c\u56fe&#xff0c;\u5982\u4f55\u8fbe\u5230<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>           1<\/p>\n<p>           \/<\/p>\n<p>           2<\/p>\n<p>          1\/2<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/2<\/span><\/span><\/span><\/span><\/span>\u8fd1\u4f3c&#xff0c;\u4f9d\u7136\u662f\u4e00\u4e2a\u516c\u5f00\u96be\u9898\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\u56e0\u6b64&#xff0c;Azarmehr\u7b49\u4eba\u7684\u5de5\u4f5c&#xff0c;\u5176\u6838\u5fc3\u76ee\u6807\u5c31\u662f\u6253\u7834\u201c\u5e38\u6570\u5ea6\u201d\u5047\u8bbe\u7684\u67b7\u9501&#xff0c;\u4e3a\u4e00\u822c\u56fe\u5b9e\u73b0<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         (<\/p>\n<p>         1<\/p>\n<p>         \/<\/p>\n<p>         2<\/p>\n<p>         \u2212<\/p>\n<p>         \u03b5<\/p>\n<p>         )<\/p>\n<p>        (1\/2-\\\\varepsilon)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\">1\/2<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u8fd1\u4f3c&#xff0c;\u4ece\u800c\u4e00\u4e3e\u5339\u914d\u7406\u8bba\u4e0b\u754c&#xff0c;\u7ec8\u7ed3\u8fd9\u573a\u8ffd\u9010\u3002<\/p>\n<h3>\u4e8c\u3001 \u6280\u672f\u84dd\u56fe&#xff1a;\u4ece\u79bb\u7ebf\u3001\u5206\u5e03\u5f0f\u5230\u6d41\u5f0f<\/h3>\n<p>\u8981\u7406\u89e3\u672c\u6587\u7684\u7a81\u7834&#xff0c;\u9996\u5148\u8981\u7406\u6e05\u5176\u6280\u672f\u4f20\u627f\u7684\u8109\u7edc\u3002\u8bba\u6587\u7684\u6838\u5fc3\u662f\u5c06\u4e00\u4e2a\u9ad8\u6548\u7684\u79bb\u7ebf&#xff08;\u6216\u5206\u5e03\u5f0f&#xff09;\u7b97\u6cd5&#xff0c;\u901a\u8fc7\u7cbe\u5de7\u7684\u91c7\u6837\u548c\u4f30\u8ba1\u6280\u672f&#xff0c;\u201c\u6a21\u62df\u201d\u5230\u6d41\u5f0f\u73af\u5883\u4e2d\u3002<\/p>\n<h4>1. \u8d77\u70b9&#xff1a;\u4e00\u4e2a\u4f18\u79c0\u7684\u79bb\u7ebf\/\u5206\u5e03\u5f0f\u7b97\u6cd5<\/h4>\n<p>\u672c\u6587\u7684\u57fa\u77f3\u662fSaxena\u7b49\u4eba\u5728SODA\u201825\u5de5\u4f5c\u4e2d\u63d0\u51fa\u7684\u4e00\u4e2a**<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        k<\/p>\n<p>       k<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>\u8f6eLOCAL\u5206\u5e03\u5f0f\u7b97\u6cd5**\u3002\u8be5\u7b97\u6cd5\u672c\u8eab\u6e90\u81ea\u5bf9\u7ecf\u5178\u8d2a\u5fc3\u7b97\u6cd5\u7684\u5206\u5e03\u5f0f\u5316&#xff08;Censor-Hillel\u7b49\u4eba&#xff09;&#xff1a;<\/p>\n<li>\u9876\u70b9\u7740\u8272&#xff1a;\u9996\u5148\u7528<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         k<\/p>\n<p>         &#061;<\/p>\n<p>         O<\/p>\n<p>         (<\/p>\n<p>         1<\/p>\n<p>         \/<\/p>\n<p>         \u03b5<\/p>\n<p>         )<\/p>\n<p>        k &#061; O(1\/\\\\varepsilon)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">&#061;<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord\">1\/<\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u79cd\u989c\u8272\u5bf9\u56fe\u8fdb\u884c\u7740\u8272&#xff0c;\u5e76\u5220\u9664\u540c\u8272\u9876\u70b9\u95f4\u7684\u8fb9&#xff08;\u8fd9\u4ec5\u635f\u5931<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         O<\/p>\n<p>         (<\/p>\n<p>         \u03b5<\/p>\n<p>         m<\/p>\n<p>         )<\/p>\n<p>        O(\\\\varepsilon m)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mord mathnormal\">m<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u6761\u8fb9&#xff0c;\u5bf9\u6700\u5927\u5272\u503c\u5f71\u54cd\u53ef\u63a7&#xff09;\u3002\u8fd9\u786e\u4fdd\u4e86\u7740\u8272\u662f\u201cproper\u201d\u7684&#xff0c;\u5373\u76f8\u90bb\u9876\u70b9\u989c\u8272\u4e0d\u540c\u3002<\/li>\n<li>\u6309\u989c\u8272\u987a\u5e8f\u5904\u7406&#xff1a;\u7b97\u6cd5\u6309\u989c\u8272\u4ece\u4f4e\u5230\u9ad8\u5904\u7406\u9876\u70b9\u3002\u6bcf\u4e2a\u9876\u70b9<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span>\u7684\u51b3\u7b56&#xff08;\u5373\u5b83\u88ab\u5206\u914d\u5230\u5272\u7684\u201c\u6e90\u4fa7\u201d\u7684\u6982\u7387<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         f<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>         \u2208<\/p>\n<p>         [<\/p>\n<p>         0<\/p>\n<p>         &#xff0c;<\/p>\n<p>         1<\/p>\n<p>         ]<\/p>\n<p>        f(v) \\\\in [0&#xff0c;1]<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1076em\">f<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">\u2208<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">[<\/span><span class=\"mord\">0<\/span><span class=\"mord cjk_fallback\">&#xff0c;<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">]<\/span><\/span><\/span><\/span><\/span>&#xff09;\u4f9d\u8d56\u4e8e\u4e24\u90e8\u5206\u4fe1\u606f&#xff1a; <\/p>\n<ul>\n<li>\u5c40\u90e8\u5ea6\u4fe1\u606f&#xff1a;\u6307\u5411\u66f4\u9ad8\u989c\u8272\u90bb\u5c45\u7684\u8fb9\u6570&#xff08;E_hi&#xff09;\u548c\u6307\u5411\u66f4\u4f4e\u989c\u8272\u90bb\u5c45\u7684\u8fb9\u6570&#xff08;E_lo&#xff09;\u3002<\/li>\n<li>\u4f4e\u9636\u90bb\u5c45\u7684\u805a\u5408\u4fe1\u606f&#xff1a;\u6240\u6709\u989c\u8272\u4f4e\u4e8e<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           v<\/p>\n<p>          v<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span>\u7684\u90bb\u5c45\u9876\u70b9\u7684<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>           f<\/p>\n<p>           (<\/p>\n<p>           u<\/p>\n<p>           )<\/p>\n<p>          f(u)<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1076em\">f<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u7684\u5e73\u5747\u503c\u3002<\/li>\n<\/ul>\n<\/li>\n<li>\u9012\u63a8\u8ba1\u7b97&#xff1a;\u901a\u8fc7\u4e00\u4e2a\u786e\u5b9a\u7684\u516c\u5f0f&#xff0c;\u53ef\u4ee5\u9012\u5f52\u5730\u8ba1\u7b97\u51fa\u6bcf\u4e2a\u9876\u70b9\u7684\u6700\u4f18&#xff08;\u6216\u8fd1\u4f3c\u6700\u4f18&#xff09;\u5206\u6570\u503c pos(v)\u3002\u7406\u8bba\u4fdd\u8bc1\u8fd9\u4e2a\u5206\u6570\u65b9\u6848\u80fd\u5b9e\u73b0<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         (<\/p>\n<p>          1<\/p>\n<p>          2<\/p>\n<p>         \u2212<\/p>\n<p>         \u03b1<\/p>\n<p>         )<\/p>\n<p>        (\\\\frac{1}{2} &#8211; \\\\alpha)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.1901em;vertical-align: -0.345em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mopen nulldelimiter\"><\/span><span class=\"mfrac\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8451em\"><span class=\"\" style=\"top: -2.655em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><span class=\"\" style=\"top: -3.23em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"frac-line\" style=\"border-bottom-width: 0.04em\"><\/span><\/span><span class=\"\" style=\"top: -3.394em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.345em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><span class=\"mclose nulldelimiter\"><\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0037em\">\u03b1<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u7684\u8fd1\u4f3c\u6bd4\u3002<\/li>\n<p>\u8fd9\u4e2aLOCAL\u7b97\u6cd5\u7684\u7f8e\u5999\u4e4b\u5904\u5728\u4e8e&#xff0c;\u51b3\u5b9a\u4e00\u4e2a\u9876\u70b9pos(v)\u503c\u6240\u9700\u7684\u4fe1\u606f&#xff0c;\u5b8c\u5168\u5305\u542b\u5728\u5b83\u7684**<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        k<\/p>\n<p>       k<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>\u8df3\u90bb\u5c45**\u4e4b\u5185\u3002<\/p>\n<h4>2. \u76f4\u63a5\u6a21\u62df\u7684\u56f0\u5883\u4e0e\u5e38\u6570\u5ea6\u5047\u8bbe<\/h4>\n<p>\u4e00\u4e2a\u6734\u7d20\u7684\u60f3\u6cd5\u662f&#xff1a;\u5728\u6d41\u5f0f\u573a\u666f\u4e2d&#xff0c;\u6211\u4eec\u80fd\u5426\u4e3a\u6bcf\u4e2a\u9876\u70b9\u6536\u96c6\u5176<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        k<\/p>\n<p>       k<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>\u8df3\u90bb\u5c45\u7684\u6240\u6709\u4fe1\u606f&#xff0c;\u7136\u540e\u5728\u672c\u5730\u6a21\u62df\u8fd9\u4e2aLOCAL\u7b97\u6cd5&#xff1f;\u5bf9\u4e8e**\u5e38\u6570\u6700\u5927\u5ea6<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        \u0394<\/p>\n<p>       \\\\Delta<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord\">\u0394<\/span><\/span><\/span><\/span><\/span>**\u7684\u56fe&#xff0c;\u8fd9\u770b\u4f3c\u53ef\u884c&#xff1a;<\/p>\n<ul>\n<li>\u6bcf\u4e2a\u9876\u70b9\u7684<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         k<\/p>\n<p>        k<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>\u8df3\u90bb\u5c45\u5b50\u56fe\u5927\u5c0f\u6700\u591a\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         O<\/p>\n<p>         (<\/p>\n<p>          \u0394<\/p>\n<p>          k<\/p>\n<p>         )<\/p>\n<p>        O(\\\\Delta^k)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0991em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord\">\u0394<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8491em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u8fd9\u662f\u4e00\u4e2a\u5e38\u6570\u3002<\/li>\n<li>\u5982\u679c\u6211\u4eec\u4ee5\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          n<\/p>\n<p>           \u2212<\/p>\n<p>           c<\/p>\n<p>        n^{-c}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.7713em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7713em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u91c7\u6837\u9876\u70b9&#xff0c;\u5e76\u5b8c\u5168\u5b58\u50a8\u88ab\u91c7\u6837\u9876\u70b9\u7684\u6240\u6709\u90bb\u8fb9&#xff0c;\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f\u4e00\u4e2a\u9876\u70b9&#xff0c;\u6211\u4eec\u5b8c\u6574\u6536\u96c6\u5176<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         k<\/p>\n<p>        k<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>\u8df3\u90bb\u5c45\u4fe1\u606f\u7684\u6982\u7387\u7ea6\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          n<\/p>\n<p>           \u2212<\/p>\n<p>           c<\/p>\n<p>           \u22c5<\/p>\n<p>           O<\/p>\n<p>           (<\/p>\n<p>            \u0394<\/p>\n<p>            k<\/p>\n<p>           )<\/p>\n<p>        n^{-c \\\\cdot O(\\\\Delta^k)}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0119em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 1.0119em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><span class=\"mbin mtight\">\u22c5<\/span><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">\u0394<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.927em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n<li>\u901a\u8fc7\u8bbe\u7f6e\u5408\u9002\u7684<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         c<\/p>\n<p>        c<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">c<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u6211\u4eec\u53ef\u4ee5\u4fdd\u8bc1\u6709\u8db3\u591f\u591a\u7684\u9876\u70b9&#xff08;\u53ca\u5176\u90bb\u5c45&#xff09;\u88ab\u6210\u529f\u91c7\u6837&#xff0c;\u4ece\u800c\u4f30\u8ba1\u51fa\u5168\u5c40\u7684\u5272\u503c\u3002\u8fd9\u6b63\u662f\u5148\u524d\u5de5\u4f5c\u5728\u5e38\u6570\u5ea6\u5047\u8bbe\u4e0b\u6210\u529f\u7684\u539f\u56e0\u3002<\/li>\n<\/ul>\n<p>\u7136\u800c&#xff0c;\u5bf9\u4e8e\u4e00\u822c\u56fe&#xff0c;\u4e00\u4e2a\u9876\u70b9\u53ef\u80fd\u62e5\u6709\u9ad8\u8fbe<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        \u03a9<\/p>\n<p>        (<\/p>\n<p>        n<\/p>\n<p>        )<\/p>\n<p>       \\\\Omega(n)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">\u03a9<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">n<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u7684\u90bb\u5c45\u3002\u5176<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        k<\/p>\n<p>       k<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>\u8df3\u9012\u5f52\u6811&#xff08;Recursion Tree&#xff09;\u7684\u5927\u5c0f\u53ef\u80fd\u662f\u6307\u6570\u7ea7\u5de8\u5927\u7684&#xff0c;\u6839\u672c\u65e0\u6cd5\u5728\u6b21\u7ebf\u6027\u7a7a\u95f4\u5185\u5b58\u50a8\u6216\u91c7\u6837\u3002\u8fd9\u4fbf\u662f\u6700\u5927\u7684\u6280\u672f\u969c\u788d\u3002<\/p>\n<h3>\u4e09\u3001 \u672c\u6587\u7684\u6838\u5fc3\u521b\u65b0&#xff1a;\u9a6f\u670d\u9ad8\u3001\u4f4e\u5ea6\u9876\u70b9<\/h3>\n<p>\u672c\u6587\u7684\u8f89\u714c\u6210\u5c31&#xff0c;\u5728\u4e8e\u8bbe\u8ba1\u4e86\u4e00\u5957\u7cbe\u5bc6\u7684\u673a\u5236\u6765\u533a\u5206\u5e76\u5904\u7406\u9ad8\u3001\u4f4e\u5ea6\u9876\u70b9&#xff0c;\u5e76\u4e25\u683c\u63a7\u5236\u4f30\u8ba1\u8fc7\u7a0b\u4e2d\u7684\u76f8\u5173\u6027&#xff08;Correlation&#xff09;\u3002\u4ee5\u4e0b\u662f\u5176\u6280\u672f\u6846\u67b6\u7684\u5206\u89e3\u3002<\/p>\n<h4>1. \u9884\u5904\u7406\u4e0e\u7b80\u5316<\/h4>\n<p>\u9996\u5148&#xff0c;\u901a\u8fc7\u4e00\u7cfb\u5217\u6807\u51c6\u4f46\u5173\u952e\u7684\u56fe\u9884\u5904\u7406\u64cd\u4f5c&#xff08;\u8fb9\u91c7\u6837\u3001\u968f\u673a\u7ffb\u8f6c\u8fb9\u65b9\u5411\u3001\u968f\u673a\u7740\u8272&#xff09;&#xff0c;\u53ef\u4ee5\u5728\u4ec5\u635f\u5931<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        O<\/p>\n<p>        (<\/p>\n<p>        \u03b5<\/p>\n<p>        )<\/p>\n<p>       O(\\\\varepsilon)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u8fd1\u4f3c\u6bd4\u7684\u524d\u63d0\u4e0b&#xff0c;\u5c06\u539f\u56fe\u8f6c\u6362\u6210\u4e00\u4e2a\u6ee1\u8db3\u4ee5\u4e0b\u4e09\u4e2a\u597d\u6027\u8d28\u7684\u7740\u8272\u56fe <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         G<\/p>\n<p>         \u2032<\/p>\n<p>       G&#039;<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.7519em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">G<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7519em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2032<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>&#xff1a;<\/p>\n<li>\u8fb9\u6570\u9002\u4e2d&#xff1a;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         m<\/p>\n<p>        m<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">m<\/span><\/span><\/span><\/span><\/span>\u5728<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          n<\/p>\n<p>           1<\/p>\n<p>           \u2212<\/p>\n<p>           c<\/p>\n<p>        n^{1-c}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.8141em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u548c<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         O<\/p>\n<p>         (<\/p>\n<p>         n<\/p>\n<p>         \/<\/p>\n<p>          \u03b5<\/p>\n<p>          4<\/p>\n<p>         )<\/p>\n<p>        O(n\/\\\\varepsilon^4)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0641em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">n<\/span><span class=\"mord\">\/<\/span><span class=\"mord\"><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u4e4b\u95f4\u3002<\/li>\n<li>\u9ad8\u5ea6\u9876\u70b9\u5e73\u8861&#xff1a;\u5bf9\u4e8e\u5ea6\u6570\u8db3\u591f\u5927\u7684\u9876\u70b9&#xff0c;\u5176\u5165\u5ea6\u548c\u51fa\u5ea6\u90fd\u81f3\u5c11\u662f\u603b\u5ea6\u6570\u7684<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          \u03b5<\/p>\n<p>          2<\/p>\n<p>        \\\\varepsilon^2<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.8141em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u500d\u3002<\/li>\n<li>\u989c\u8272\u5206\u5e03\u5747\u5300&#xff1a;\u5bf9\u4e8e\u4e00\u4e2a\u9ad8\u5ea6\u9876\u70b9&#xff0c;\u5176\u90bb\u5c45\u7684\u989c\u8272\u5206\u5e03\u5927\u81f4\u5747\u5300\u3002 \u8fd9\u4e9b\u6027\u8d28\u6781\u5927\u5730\u7b80\u5316\u4e86\u540e\u7eed\u7684\u5206\u6790&#xff0c;\u4f7f\u6211\u4eec\u80fd\u4e13\u6ce8\u4e8e\u7b97\u6cd5\u6838\u5fc3\u3002<\/li>\n<h4>2. \u9876\u70b9\u7684\u4e8c\u5143\u5206\u7c7b&#xff1a;\u9ad8\u3001\u4f4e\u5ea6\u65b0\u5b9a\u4e49<\/h4>\n<p>\u672c\u6587\u5bf9\u201c\u9ad8\u3001\u4f4e\u5ea6\u201d\u7684\u5b9a\u4e49\u975e\u5e38\u5de7\u5999&#xff0c;\u4e0d\u662f\u57fa\u4e8e\u7edd\u5bf9\u5e38\u6570&#xff0c;\u800c\u662f\u57fa\u4e8e\u989c\u8272\u548c\u6307\u6570\u7ea7\u589e\u957f\u7684\u95e8\u69db\u3002 \u5bf9\u4e8e\u4e00\u4e2a\u989c\u8272\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        a<\/p>\n<p>       a<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">a<\/span><\/span><\/span><\/span><\/span> \u7684\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        v<\/p>\n<p>       v<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u6211\u4eec\u8bbe\u5b9a\u4e00\u4e2a\u9608\u503c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         n<\/p>\n<p>          q<\/p>\n<p>          \u22c5<\/p>\n<p>           2<\/p>\n<p>           a<\/p>\n<p>       n^{q \\\\cdot 2^{a}}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.88em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.88em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"mbin mtight\">\u22c5<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7385em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">a<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> &#xff08;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        q<\/p>\n<p>       q<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.625em;vertical-align: -0.1944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><\/span><\/span><\/span><\/span>\u662f\u4e00\u4e2a\u4f9d\u8d56\u4e8e<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        \u03b5<\/p>\n<p>       \\\\varepsilon<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">\u03b5<\/span><\/span><\/span><\/span><\/span>\u7684\u5c0f\u5e38\u6570&#xff09;\u3002\u5982\u679c\u5176&#xff08;\u901a\u8fc7\u91c7\u6837\u4f30\u8ba1\u7684&#xff09;\u5ea6\u6570\u9ad8\u4e8e\u6b64\u9608\u503c&#xff0c;\u5219\u89c6\u4e3a\u9ad8\u5ea6\u9876\u70b9&#xff0c;\u5426\u5219\u4e3a\u4f4e\u5ea6\u9876\u70b9\u3002\u8fd9\u4e2a\u9608\u503c\u968f\u7740\u989c\u8272<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        a<\/p>\n<p>       a<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">a<\/span><\/span><\/span><\/span><\/span>\u53cc\u6307\u6570\u589e\u957f&#xff0c;\u662f\u540e\u7eed\u63a7\u5236\u76f8\u5173\u6027\u7684\u5173\u952e\u3002<\/p>\n<h4>3. \u4f4e\u5ea6\u9876\u70b9&#xff1a;\u7a00\u758f\u5316\u9012\u5f52\u6811\u4e0e\u201c\u6210\u529f\u201d\u94fe<\/h4>\n<p>\u5bf9\u4e8e\u4f4e\u5ea6\u9876\u70b9&#xff0c;\u7b97\u6cd5\u91c7\u53d6\u7684\u7b56\u7565\u662f\u7a00\u758f\u5316\u5176\u5e9e\u5927\u7684\u9012\u5f52\u6811\u3002<\/p>\n<ul>\n<li>\u9876\u70b9\u91c7\u6837&#xff1a;\u4ee5\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          n<\/p>\n<p>           \u2212<\/p>\n<p>           c<\/p>\n<p>        n^{-c}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.7713em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7713em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u72ec\u7acb\u91c7\u6837\u4e00\u4e2a\u9876\u70b9\u96c6\u5408 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         W<\/p>\n<p>        W<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span>\u3002\u5bf9\u4e8e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         W<\/p>\n<p>        W<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span> \u4e2d\u7684\u9876\u70b9&#xff0c;\u6211\u4eec\u7cbe\u786e\u8bb0\u5f55\u5176\u5404\u7c7b\u5ea6\u4fe1\u606f\u3002<\/li>\n<li>\u90bb\u5c45\u91c7\u6837&#xff1a;\u5bf9\u4e8e\u6bcf\u4e2a\u88ab\u91c7\u6837\u7684\u4f4e\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u6211\u4eec\u4ece\u5176\u6307\u5411\u4f4e\u8272\u90bb\u5c45\u7684\u8fb9&#xff08;E_lo_in\u548cE_lo_out&#xff09;\u4e2d&#xff0c;\u5404\u5747\u5300\u62bd\u53d6<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          d<\/p>\n<p>          &#061;<\/p>\n<p>           O<\/p>\n<p>           \u03b5<\/p>\n<p>          (<\/p>\n<p>          1<\/p>\n<p>          )<\/p>\n<p>         d &#061; O_{\\\\varepsilon}(1)<\/p>\n<p>      <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\">d<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">&#061;<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0278em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">\u03b5<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord\">1<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u6761\u8fb9&#xff08;\u6709\u653e\u56de&#xff09;&#xff0c;\u8bb0\u4f5c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          R<\/p>\n<p>           i<\/p>\n<p>           n<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        R_{in}(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0077em\">R<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3117em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0077em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">in<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u548c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          R<\/p>\n<p>           o<\/p>\n<p>           u<\/p>\n<p>           t<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        R_{out}(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0077em\">R<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.2806em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0077em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">o<\/span><span class=\"mord mathnormal mtight\">u<\/span><span class=\"mord mathnormal mtight\">t<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u3002\u8fd9<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         d<\/p>\n<p>        d<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\">d<\/span><\/span><\/span><\/span><\/span>\u4e2a\u88ab\u9009\u4e2d\u7684\u90bb\u5c45\u79f0\u4e3a\u201c\u9009\u5b9a\u90bb\u5c45\u201d\u3002<\/li>\n<li>\u4f30\u8ba1\u4e0e\u6210\u529f\u6761\u4ef6&#xff1a;\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span> \u7684\u4f30\u8ba1\u4f4d\u7f6e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        P(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u4f9d\u8d56\u4e8e\u5176\u7cbe\u786e\u7684\u5ea6\u4fe1\u606f\u548c\u8fd9<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         d<\/p>\n<p>        d<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\">d<\/span><\/span><\/span><\/span><\/span>\u4e2a\u9009\u5b9a\u90bb\u5c45\u7684\u4f30\u8ba1\u4f4d\u7f6e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         u<\/p>\n<p>         )<\/p>\n<p>        P(u)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u3002\u8fd9\u5f62\u6210\u4e86\u4e00\u4e2a\u4f9d\u8d56\u94fe&#xff1a;\u4e3a\u4e86\u4f30\u8ba1 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5fc5\u987b\u5148\u4f30\u8ba1\u5b83\u7684\u9009\u5b9a\u90bb\u5c45&#xff1b;\u800c\u8fd9\u4e9b\u90bb\u5c45\u7684\u4f30\u8ba1\u53c8\u4f9d\u8d56\u4e8e\u5b83\u4eec\u81ea\u5df1\u7684\u9009\u5b9a\u90bb\u5c45\u3002<\/li>\n<li>\u5b9a\u4e49\u6210\u529f&#xff1a;\u6211\u4eec\u8bf4\u4e00\u4e2a\u4f4e\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span> \u201c\u6210\u529f\u201d&#xff0c;\u5f53\u4e14\u4ec5\u5f53\u5b83\u88ab\u91c7\u6837&#xff08;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>         \u2208<\/p>\n<p>         W<\/p>\n<p>        v \\\\in W<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.5782em;vertical-align: -0.0391em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">\u2208<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span>&#xff09;&#xff0c;\u5e76\u4e14\u5b83\u7684\u6240\u6709\u9009\u5b9a\u90bb\u5c45\u4e5f\u90fd\u201c\u6210\u529f\u201d\u3002\u8fd9\u610f\u5473\u7740\u6211\u4eec\u9700\u8981\u6cbf\u7740\u8fd9\u6761\u7a00\u758f\u5316\u7684\u4f9d\u8d56\u6811&#xff0c;\u4ece\u6811\u6839&#xff08;\u9ad8\u989c\u8272\u9876\u70b9&#xff09;\u5230\u6811\u53f6&#xff08;\u989c\u8272\u4e3a1\u7684\u9876\u70b9&#xff09;&#xff0c;\u4e00\u8def\u4e0a\u7684\u6240\u6709\u9876\u70b9\u90fd\u6070\u597d\u88ab\u91c7\u6837\u4e86\u3002\u7531\u4e8e\u6811\u7684\u6df1\u5ea6\u6700\u591a\u4e3a<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         k<\/p>\n<p>        k<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u6bcf\u4e2a\u8282\u70b9\u6700\u591a\u6709<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         d<\/p>\n<p>        d<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6944em\"><\/span><span class=\"mord mathnormal\">d<\/span><\/span><\/span><\/span><\/span>\u4e2a\u5b50\u8282\u70b9&#xff0c;\u8fd9\u68f5\u7a00\u758f\u6811\u7684\u5927\u5c0f\u662f\u5e38\u6570 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          T<\/p>\n<p>           m<\/p>\n<p>           a<\/p>\n<p>           x<\/p>\n<p>         &#061;<\/p>\n<p>         O<\/p>\n<p>         (<\/p>\n<p>          d<\/p>\n<p>          k<\/p>\n<p>         )<\/p>\n<p>        T_{max} &#061; O(d^k)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.8333em;vertical-align: -0.15em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">T<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.1389em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">ma<\/span><span class=\"mord mathnormal mtight\">x<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">&#061;<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1.0991em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">d<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8491em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0315em\">k<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u3002\u56e0\u6b64&#xff0c;\u4e00\u4e2a\u9876\u70b9\u6210\u529f\u7684\u6982\u7387\u662f <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          n<\/p>\n<p>           \u2212<\/p>\n<p>           c<\/p>\n<p>            T<\/p>\n<p>             m<\/p>\n<p>             a<\/p>\n<p>             x<\/p>\n<p>        n^{-c T_{max}}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.8413em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8413em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.1389em\">T<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1645em\"><span class=\"\" style=\"top: -2.357em;margin-left: -0.1389em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">ma<\/span><span class=\"mord mathnormal mtight\">x<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.143em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>&#xff0c;\u8fd9\u662f\u53ef\u63a7\u7684\u3002<\/li>\n<\/ul>\n<h4>4. \u9ad8\u5ea6\u9876\u70b9&#xff1a;\u57fa\u4e8e\u5168\u5c40\u91c7\u6837\u7684\u7a33\u5b9a\u4f30\u8ba1<\/h4>\n<p>\u9ad8\u5ea6\u9876\u70b9\u7684\u5904\u7406\u65b9\u5f0f\u622a\u7136\u4e0d\u540c&#xff0c;\u5b83\u4eec\u603b\u662f\u201c\u6210\u529f\u201d\u7684\u3002<\/p>\n<ul>\n<li>\u7b97\u6cd5\u4f1a\u72ec\u7acb\u5730\u4ee5\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          n<\/p>\n<p>           \u2212<\/p>\n<p>           c<\/p>\n<p>        n^{-c}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.7713em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7713em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u91c7\u6837\u5168\u5c40\u8fb9\u96c6 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         B<\/p>\n<p>        \\\\mathbf{B}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span>\u3002\u5bf9\u4e8e\u4e00\u4e2a\u9ad8\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5176\u5728 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         B<\/p>\n<p>        \\\\mathbf{B}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span> \u4e2d\u7684\u90bb\u5c45\u6837\u672c\u91cf\u975e\u5e38\u5927&#xff08;\u8d85\u8fc7\u9608\u503c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          n<\/p>\n<p>           q<\/p>\n<p>           \u22c5<\/p>\n<p>            2<\/p>\n<p>            a<\/p>\n<p>        n^{q \\\\cdot 2^{a}}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.88em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.88em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"mbin mtight\">\u22c5<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7385em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">a<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>&#xff09;\u3002<\/li>\n<li>\u5ea6\u4fe1\u606f\u4f30\u8ba1&#xff1a;\u5229\u7528 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         B<\/p>\n<p>        \\\\mathbf{B}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span> \u4e2d\u7684\u8fb9&#xff0c;\u6211\u4eec\u53ef\u4ee5\u9ad8\u7cbe\u5ea6\u5730\u4f30\u8ba1\u51fa <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span> \u7684\u5165\u5ea6\u3001\u51fa\u5ea6\u6bd4\u4f8b <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>            d<\/p>\n<p>            &#043;<\/p>\n<p>           (<\/p>\n<p>           v<\/p>\n<p>           )<\/p>\n<p>           d<\/p>\n<p>           (<\/p>\n<p>           v<\/p>\n<p>           )<\/p>\n<p>        \\\\frac{d^{&#043;}(v)}{d(v)}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.5984em;vertical-align: -0.52em\"><\/span><span class=\"mord\"><span class=\"mopen nulldelimiter\"><\/span><span class=\"mfrac\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 1.0784em\"><span class=\"\" style=\"top: -2.655em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">d<\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><span class=\"\" style=\"top: -3.23em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"frac-line\" style=\"border-bottom-width: 0.04em\"><\/span><\/span><span class=\"\" style=\"top: -3.485em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">d<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8477em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">&#043;<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.52em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><span class=\"mclose nulldelimiter\"><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n<li>\u90bb\u5c45\u4f4d\u7f6e\u4f30\u8ba1&#xff1a;\u4e3a\u4e86\u4f30\u8ba1\u4f4e\u8272\u90bb\u5c45\u7684\u5e73\u5747\u4f4d\u7f6e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          z<\/p>\n<p>          \u203e<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        \\\\overline{z}(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord overline\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.6306em\"><span class=\"\" style=\"top: -3em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.044em\">z<\/span><\/span><\/span><span class=\"\" style=\"top: -3.5506em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"overline-line\" style=\"border-bottom-width: 0.04em\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u7b97\u6cd5\u4f1a\u67e5\u770b <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         B<\/p>\n<p>        \\\\mathbf{B}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span> \u4e2d\u6240\u6709\u989c\u8272\u4f4e\u4e8e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span> \u7684\u90bb\u5c45\u3002\u5bf9\u4e8e\u6bcf\u4e2a\u8fd9\u6837\u7684\u90bb\u5c45 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         u<\/p>\n<p>        u<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">u<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u7b97\u6cd5\u5c06\u5176\u4f30\u8ba1\u503c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         u<\/p>\n<p>         )<\/p>\n<p>        P(u)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff08;\u5982\u679c<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         u<\/p>\n<p>        u<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">u<\/span><\/span><\/span><\/span><\/span>\u6210\u529f&#xff09;\u8fde\u540c\u5176\u6210\u529f\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          q<\/p>\n<p>          u<\/p>\n<p>        q_u<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.625em;vertical-align: -0.1944em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">u<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u4e00\u8d77&#xff0c;\u9001\u5165\u4e00\u4e2a Horvitz-Thompson\u4f30\u8ba1\u5668\u3002<\/li>\n<li>Horvitz-Thompson\u4f30\u8ba1\u5668&#xff1a;\u8fd9\u662f\u4e00\u4e2a\u7edf\u8ba1\u5b66\u4e2d\u5904\u7406\u7f3a\u5931\u6570\u636e\u7684\u7ecf\u5178\u65b9\u6cd5\u3002\u5176\u6838\u5fc3\u601d\u60f3\u662f&#xff0c;\u5982\u679c\u4e00\u4e2a\u503c\u4ee5\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         q<\/p>\n<p>        q<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.625em;vertical-align: -0.1944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><\/span><\/span><\/span><\/span> \u88ab\u89c2\u6d4b\u5230&#xff0c;\u90a3\u4e48\u5728\u6c42\u548c\u65f6\u5c06\u5176\u8d21\u732e\u9664\u4ee5 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         q<\/p>\n<p>        q<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.625em;vertical-align: -0.1944em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5c31\u80fd\u5728\u671f\u671b\u4e0a\u8865\u507f\u90a3\u4e9b\u672a\u88ab\u89c2\u6d4b\u5230\u7684\u6837\u672c&#xff0c;\u4ece\u800c\u83b7\u5f97\u65e0\u504f\u4f30\u8ba1\u3002\u5728\u672c\u6587\u4e2d&#xff0c;\u5bf9\u4e8e\u9ad8\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span> \u7684\u90bb\u5c45 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         u<\/p>\n<p>        u<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">u<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u7b97\u6cd5\u8ba1\u7b97 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         u<\/p>\n<p>         )<\/p>\n<p>         \/<\/p>\n<p>          q<\/p>\n<p>          u<\/p>\n<p>        P(u)\/q_u<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><span class=\"mord\">\/<\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">u<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u6837\u672c\u5747\u503c\u6765\u4f30\u8ba1 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          z<\/p>\n<p>          \u203e<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        \\\\overline{z}(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord overline\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.6306em\"><span class=\"\" style=\"top: -3em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.044em\">z<\/span><\/span><\/span><span class=\"\" style=\"top: -3.5506em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"overline-line\" style=\"border-bottom-width: 0.04em\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n<\/ul>\n<h4>5. \u6700\u5927\u6311\u6218&#xff1a;\u63a7\u5236\u76f8\u5173\u6027\u7206\u70b8<\/h4>\n<p>\u4e0a\u8ff0\u6846\u67b6\u542c\u8d77\u6765\u5408\u7406&#xff0c;\u4f46\u4e00\u4e2a\u5de8\u5927\u7684\u9677\u9631\u6f5c\u4f0f\u5176\u4e2d&#xff1a;\u76f8\u5173\u6027\u3002\u8003\u8651\u4e24\u4e2a\u9ad8\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>         1<\/p>\n<p>       v_1<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.5806em;vertical-align: -0.15em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3011em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u548c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         v<\/p>\n<p>         2<\/p>\n<p>       v_2<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.5806em;vertical-align: -0.15em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3011em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5b83\u4eec\u53ef\u80fd\u5171\u4eab\u8bb8\u591a\u4f4e\u5ea6\u90bb\u5c45\u3002\u8fd9\u4e9b\u4f4e\u5ea6\u90bb\u5c45\u7684\u4f30\u8ba1\u503c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        P<\/p>\n<p>        (<\/p>\n<p>        u<\/p>\n<p>        )<\/p>\n<p>       P(u)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u672c\u8eab\u662f\u9ad8\u5ea6\u76f8\u5173\u7684&#xff0c;\u56e0\u4e3a\u5b83\u4eec\u7684\u201c\u6210\u529f\u201d\u4f9d\u8d56\u4e8e\u540c\u4e00\u68f5\u7a00\u758f\u91c7\u6837\u6811\u3002 \u66f4\u5371\u9669\u7684\u662f&#xff0c;\u5728Horvitz-Thompson\u4f30\u8ba1\u4e2d&#xff0c;\u8fd9\u4e9b\u4f30\u8ba1\u503c\u4f1a\u88ab\u9664\u4ee5\u4e00\u4e2a\u5f88\u5c0f\u7684\u6210\u529f\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         q<\/p>\n<p>         u<\/p>\n<p>        \u2248<\/p>\n<p>         n<\/p>\n<p>          \u2212<\/p>\n<p>          c<\/p>\n<p>           T<\/p>\n<p>            m<\/p>\n<p>            a<\/p>\n<p>            x<\/p>\n<p>       q_u \\\\approx n^{-c T_{max}}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6776em;vertical-align: -0.1944em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">u<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">\u2248<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 0.8413em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8413em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.1389em\">T<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1645em\"><span class=\"\" style=\"top: -2.357em;margin-left: -0.1389em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">ma<\/span><span class=\"mord mathnormal mtight\">x<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.143em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u8fd9\u610f\u5473\u7740&#xff0c;\u5373\u4f7f <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        P<\/p>\n<p>        (<\/p>\n<p>        u<\/p>\n<p>        )<\/p>\n<p>       P(u)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u672c\u8eab\u7684\u65b9\u5dee\u5f88\u5c0f&#xff0c;\u7f29\u653e\u540e\u7684\u53d8\u91cf <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        P<\/p>\n<p>        (<\/p>\n<p>        u<\/p>\n<p>        )<\/p>\n<p>        \/<\/p>\n<p>         q<\/p>\n<p>         u<\/p>\n<p>       P(u)\/q_u<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><span class=\"mord\">\/<\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">u<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u65b9\u5dee\u4f1a\u88ab\u653e\u5927 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        1<\/p>\n<p>        \/<\/p>\n<p>         q<\/p>\n<p>         u<\/p>\n<p>         2<\/p>\n<p>        \u2248<\/p>\n<p>         n<\/p>\n<p>          2<\/p>\n<p>          c<\/p>\n<p>           T<\/p>\n<p>            m<\/p>\n<p>            a<\/p>\n<p>            x<\/p>\n<p>       1\/q_u^2 \\\\approx n^{2c T_{max}}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0641em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/<\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -2.453em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">u<\/span><\/span><\/span><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.247em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">\u2248<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 0.8413em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8413em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><span class=\"mord mathnormal mtight\">c<\/span><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.1389em\">T<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1645em\"><span class=\"\" style=\"top: -2.357em;margin-left: -0.1389em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">ma<\/span><span class=\"mord mathnormal mtight\">x<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.143em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u500d&#xff01;\u5982\u679c\u5904\u7406\u4e0d\u5f53&#xff0c;\u8fd9\u79cd\u201c\u76f8\u5173\u6027\u7206\u70b8\u201d\u4f1a\u5f7b\u5e95\u6467\u6bc1\u4f30\u8ba1\u7684\u51c6\u786e\u6027\u3002<\/p>\n<p>\u672c\u6587\u6700\u7cbe\u5999\u7684\u5206\u6790\u5c31\u5728\u4e8e\u6210\u529f\u9a6f\u670d\u4e86\u8fd9\u79cd\u76f8\u5173\u6027\u3002\u5176\u6838\u5fc3\u6d1e\u5bdf\u662f&#xff1a;<\/p>\n<li>\u4f4e\u5ea6\u9876\u70b9\u6811\u7684\u5927\u5c0f\u9650\u5236&#xff1a;\u7531\u4e8e\u4f4e\u5ea6\u9876\u70b9\u7684\u5ea6\u6570\u6709\u4e0a\u9650 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          n<\/p>\n<p>           q<\/p>\n<p>           \u22c5<\/p>\n<p>            2<\/p>\n<p>            a<\/p>\n<p>        n^{q \\\\cdot 2^{a}}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.88em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.88em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"mbin mtight\">\u22c5<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7385em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">a<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>&#xff0c;\u8fd9\u4f7f\u5f97\u4efb\u4f55\u4e00\u4e2a\u7279\u5b9a\u7684\u4f4e\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         w<\/p>\n<p>        w<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0269em\">w<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u4e0d\u53ef\u80fd\u51fa\u73b0\u5728\u201c\u592a\u591a\u201d\u5176\u4ed6\u9876\u70b9\u7684\u7a00\u758f\u9012\u5f52\u6811\u4e2d\u3002\u5177\u4f53\u5730&#xff0c;\u4e00\u4e2a\u989c\u8272\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         a<\/p>\n<p>        a<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">a<\/span><\/span><\/span><\/span><\/span> \u7684\u9876\u70b9&#xff0c;\u5176\u7a00\u758f\u6811\u4e2d\u7684\u8282\u70b9\u6700\u591a\u88ab <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         O<\/p>\n<p>         (<\/p>\n<p>          n<\/p>\n<p>           q<\/p>\n<p>           \u22c5<\/p>\n<p>            2<\/p>\n<p>             a<\/p>\n<p>             \u2212<\/p>\n<p>             1<\/p>\n<p>         )<\/p>\n<p>        O(n^{q \\\\cdot 2^{a-1}})<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.2369em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.9869em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"mbin mtight\">\u22c5<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8913em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">a<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mtight\">1<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u4e2a\u540c\u8272\u90bb\u5c45\u5171\u4eab\u3002<\/li>\n<li>\u9ad8\u5ea6\u9876\u70b9\u7684\u90bb\u5c45\u6570\u91cf\u4f18\u52bf&#xff1a;\u9ad8\u5ea6\u9876\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         v<\/p>\n<p>        v<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><\/span><\/span><\/span><\/span> \u7684\u90bb\u5c45\u6570\u91cf\u975e\u5e38\u5e9e\u5927&#xff08;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         \u2248<\/p>\n<p>          n<\/p>\n<p>           q<\/p>\n<p>           \u22c5<\/p>\n<p>            2<\/p>\n<p>            a<\/p>\n<p>        \\\\approx n^{q \\\\cdot 2^{a}}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4831em\"><\/span><span class=\"mrel\">\u2248<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 0.88em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.88em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\" style=\"margin-right: 0.0359em\">q<\/span><span class=\"mbin mtight\">\u22c5<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7385em\"><span class=\"\" style=\"top: -2.931em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">a<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>&#xff09;\u3002\u5f53\u5b83\u7528\u8fd9\u4e9b\u90bb\u5c45\u7684\u6837\u672c\u505a\u5e73\u5747\u65f6&#xff0c;\u5c3d\u7ba1\u6709\u4e9b\u90bb\u5c45\u7684\u4f30\u8ba1\u662f\u76f8\u5173\u7684&#xff0c;\u4f46\u76f8\u5173\u5bf9\u7684\u6570\u76ee&#xff08;\u7531\u4e0a\u4e00\u6761\u9650\u5b9a&#xff09;\u76f8\u5bf9\u4e8e\u5de8\u5927\u7684\u603b\u90bb\u5c45\u6570\u800c\u8a00\u5360\u6bd4\u5f88\u5c0f\u3002<\/li>\n<li>\u5f52\u7eb3\u5f0f\u65b9\u5dee\u63a7\u5236&#xff1a;\u4f5c\u8005\u901a\u8fc7\u590d\u6742\u7684\u5f52\u7eb3\u8bc1\u660e&#xff0c;\u4e3a\u6bcf\u4e2a\u989c\u8272 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         a<\/p>\n<p>        a<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">a<\/span><\/span><\/span><\/span><\/span> \u7684\u9876\u70b9\u5b9a\u4e49\u4e86\u4e00\u7ec4\u9012\u51cf\u7684\u65b9\u5dee\u4e0a\u754c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          \u03c3<\/p>\n<p>          a<\/p>\n<p>          2<\/p>\n<p>        \\\\sigma_a^2<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0611em;vertical-align: -0.247em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">\u03c3<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -2.453em;margin-left: -0.0359em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">a<\/span><\/span><\/span><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.247em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u548c\u504f\u5dee\u4e0a\u754c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          \u03b4<\/p>\n<p>          a<\/p>\n<p>        \\\\delta_a<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.8444em;vertical-align: -0.15em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0379em\">\u03b4<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1514em\"><span class=\"\" style=\"top: -2.55em;margin-left: -0.0379em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mathnormal mtight\">a<\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.15em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u4ed6\u4eec\u8bc1\u660e&#xff0c;\u65e0\u8bba\u9ad8\u3001\u4f4e\u5ea6\u9876\u70b9&#xff0c;\u5176\u6700\u7ec8\u4f30\u8ba1\u503c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        P(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u7684\u65b9\u5dee\u548c\u671f\u671b\u504f\u5dee\u90fd\u80fd\u88ab\u8fd9\u4e9b\u754c\u6240\u63a7\u5236\u3002\u8bc1\u660e\u8fc7\u7a0b\u4e2d&#xff0c;\u9700\u8981\u7ec6\u81f4\u5730\u5c06\u76f8\u5173\u6027\u6309\u7167\u201c\u662f\u5426\u901a\u8fc7\u9ad8\u5ea6\u9876\u70b9\u4f20\u9012\u201d\u8fdb\u884c\u5206\u7c7b\u8ba8\u8bba&#xff0c;\u5e76\u5229\u7528\u4e0a\u8ff0\u7684\u89c4\u6a21\u4f18\u52bf\u8fdb\u884c\u52a0\u548c\u7ea6\u675f\u3002<\/li>\n<h4>6. \u7b97\u6cd5\u6b65\u9aa4\u4e0e\u7a7a\u95f4\u5206\u6790<\/h4>\n<p>\u6574\u4e2a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5&#xff08;Algorithm 5&#xff09;\u7684\u6d41\u7a0b\u6e05\u6670&#xff1a;<\/p>\n<li>\u521d\u59cb\u5316&#xff1a;\u51c6\u5907\u9876\u70b9\u91c7\u6837\u96c6 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         W<\/p>\n<p>        W<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span>\u3001\u8fb9\u91c7\u6837\u96c6 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         B<\/p>\n<p>        \\\\mathbf{B}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span>\u3001\u7528\u4e8e\u6700\u7ec8\u4f30\u8ba1\u7684\u8fb9\u6c34\u5e93\u6837\u672c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         C<\/p>\n<p>        \\\\mathbf{C}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">C<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5e76\u4e3a\u6bcf\u4e2a\u53ef\u80fd\u88ab\u91c7\u6837\u7684\u9876\u70b9\u521d\u59cb\u5316\u7528\u4e8e\u8bb0\u5f55\u9009\u5b9a\u90bb\u5c45\u7684\u6c34\u5e93 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>          R<\/p>\n<p>           i<\/p>\n<p>           n<\/p>\n<p>           \/<\/p>\n<p>           o<\/p>\n<p>           u<\/p>\n<p>           t<\/p>\n<p>        R_{in\/out}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0385em;vertical-align: -0.3552em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0077em\">R<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3448em\"><span class=\"\" style=\"top: -2.5198em;margin-left: -0.0077em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">in<\/span><span class=\"mord mtight\">\/<\/span><span class=\"mord mathnormal mtight\">o<\/span><span class=\"mord mathnormal mtight\">u<\/span><span class=\"mord mathnormal mtight\">t<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3552em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n<li>\u5904\u7406\u6d41&#xff1a;\u5f53\u6bcf\u6761\u8fb9\u5230\u8fbe\u65f6&#xff1a;\n<ul>\n<li>\u4ee5\u6982\u7387 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>            n<\/p>\n<p>             \u2212<\/p>\n<p>             c<\/p>\n<p>          n^{-c}<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.7713em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.7713em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u5c06\u5176\u52a0\u5165 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>           B<\/p>\n<p>          \\\\mathbf{B}<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n<li>\u7528\u6c34\u5e93\u91c7\u6837\u7ef4\u62a4 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           C<\/p>\n<p>          \\\\mathbf{C}<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">C<\/span><\/span><\/span><\/span><\/span>\u3002<\/li>\n<li>\u5982\u679c\u8fb9\u7684\u7aef\u70b9\u5c5e\u4e8e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>           W<\/p>\n<p>          W<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u5219\u66f4\u65b0\u5176\u5ea6\u8ba1\u6570\u5668&#xff0c;\u5e76\u6839\u636e\u9876\u70b9\u989c\u8272\u5173\u7cfb&#xff0c;\u51b3\u5b9a\u662f\u5426\u5c06\u8be5\u8fb9\u5b58\u5165\u76f8\u5e94\u7aef\u70b9 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>            R<\/p>\n<p>             i<\/p>\n<p>             n<\/p>\n<p>             \/<\/p>\n<p>             o<\/p>\n<p>             u<\/p>\n<p>             t<\/p>\n<p>          R_{in\/out}<\/p>\n<p>       <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0385em;vertical-align: -0.3552em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0077em\">R<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3448em\"><span class=\"\" style=\"top: -2.5198em;margin-left: -0.0077em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">in<\/span><span class=\"mord mtight\">\/<\/span><span class=\"mord mathnormal mtight\">o<\/span><span class=\"mord mathnormal mtight\">u<\/span><span class=\"mord mathnormal mtight\">t<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3552em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7684\u6c34\u5e93\u4e2d\u3002<\/li>\n<\/ul>\n<\/li>\n<li>\u540e\u5904\u7406\u4e0e\u4f30\u8ba1&#xff1a;\u6d41\u7ed3\u675f\u540e&#xff0c;\u5bf9\u4e8e\u6c34\u5e93 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         C<\/p>\n<p>        \\\\mathbf{C}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">C<\/span><\/span><\/span><\/span><\/span> \u4e2d\u7684\u6bcf\u6761\u8fb9&#xff0c;\u8c03\u7528 EdgeEstimator\u3002\u8be5\u4f30\u8ba1\u5668\u4f1a\u9012\u5f52\u8c03\u7528 VertexEstimator \u6765\u83b7\u53d6\u8fb9\u4e24\u4e2a\u7aef\u70b9\u7684\u4f30\u8ba1\u4f4d\u7f6e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         u<\/p>\n<p>         )<\/p>\n<p>        P(u)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u548c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>        P(v)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u4ece\u800c\u5f97\u5230\u8fb9\u8d21\u732e <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         u<\/p>\n<p>         )<\/p>\n<p>         \u2217<\/p>\n<p>         (<\/p>\n<p>         1<\/p>\n<p>         \u2212<\/p>\n<p>         P<\/p>\n<p>         (<\/p>\n<p>         v<\/p>\n<p>         )<\/p>\n<p>         )<\/p>\n<p>        P(u)*(1-P(v))<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">u<\/span><span class=\"mclose\">)<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2217<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\">1<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">P<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0359em\">v<\/span><span class=\"mclose\">))<\/span><\/span><\/span><\/span><\/span>\u3002\u5982\u679c\u4efb\u4e00\u7aef\u70b9\u4f30\u8ba1\u5931\u8d25&#xff08;\u6811\u672a\u5168\u90e8\u91c7\u6837&#xff09;&#xff0c;\u5219\u6b64\u8fb9\u8d21\u732e\u8bb0\u4e3a\u5931\u8d25\u3002\u6700\u540e&#xff0c;\u4f7f\u7528Horvitz-Thompson\u4f30\u8ba1\u5668\u5bf9\u6240\u6709\u6210\u529f\u8fb9\u7684\u8d21\u732e\u6c42\u5e73\u5747&#xff0c;\u5f97\u5230\u5168\u5c40\u5272\u503c\u7684\u4f30\u8ba1 Cut-Val\u3002<\/li>\n<p>\u7a7a\u95f4\u590d\u6742\u5ea6&#xff1a;\u4e3b\u8981\u5b58\u50a8 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        W<\/p>\n<p>       W<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span>\u3001<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        B<\/p>\n<p>       \\\\mathbf{B}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">B<\/span><\/span><\/span><\/span><\/span>\u3001<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        C<\/p>\n<p>       \\\\mathbf{C}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6861em\"><\/span><span class=\"mord mathbf\">C<\/span><\/span><\/span><\/span><\/span>\u3001\u4ee5\u53ca\u6240\u6709 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         R<\/p>\n<p>          i<\/p>\n<p>          n<\/p>\n<p>          \/<\/p>\n<p>          o<\/p>\n<p>          u<\/p>\n<p>          t<\/p>\n<p>       R_{in\/out}<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0385em;vertical-align: -0.3552em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right: 0.0077em\">R<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3448em\"><span class=\"\" style=\"top: -2.5198em;margin-left: -0.0077em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">in<\/span><span class=\"mord mtight\">\/<\/span><span class=\"mord mathnormal mtight\">o<\/span><span class=\"mord mathnormal mtight\">u<\/span><span class=\"mord mathnormal mtight\">t<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.3552em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u6c34\u5e93\u3002\u5728\u9884\u5904\u7406\u540e\u56fe\u8fb9\u6570 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        m<\/p>\n<p>        &#061;<\/p>\n<p>        O<\/p>\n<p>        (<\/p>\n<p>        n<\/p>\n<p>        \/<\/p>\n<p>         \u03b5<\/p>\n<p>         4<\/p>\n<p>        )<\/p>\n<p>       m &#061; O(n\/\\\\varepsilon^4)<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.4306em\"><\/span><span class=\"mord mathnormal\">m<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><span class=\"mrel\">&#061;<\/span><span class=\"mspace\" style=\"margin-right: 0.2778em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1.0641em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord mathnormal\">n<\/span><span class=\"mord\">\/<\/span><span class=\"mord\"><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">4<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span> \u7684\u6761\u4ef6\u4e0b&#xff0c;\u6613\u8bc1 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        \u2223<\/p>\n<p>        W<\/p>\n<p>        \u2223<\/p>\n<p>        &#xff0c;<\/p>\n<p>        \u2223<\/p>\n<p>        B<\/p>\n<p>        \u2223<\/p>\n<p>        &#xff0c;<\/p>\n<p>        \u2223<\/p>\n<p>        C<\/p>\n<p>        \u2223<\/p>\n<p>       |W|&#xff0c; |\\\\mathbf{B}|&#xff0c; |\\\\mathbf{C}|<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">\u2223<\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><span class=\"mord\">\u2223<\/span><span class=\"mord cjk_fallback\">&#xff0c;<\/span><span class=\"mord\">\u2223<\/span><span class=\"mord mathbf\">B<\/span><span class=\"mord\">\u2223<\/span><span class=\"mord cjk_fallback\">&#xff0c;<\/span><span class=\"mord\">\u2223<\/span><span class=\"mord mathbf\">C<\/span><span class=\"mord\">\u2223<\/span><\/span><\/span><\/span><\/span> \u7684\u671f\u671b\u5927\u5c0f\u5747\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        O<\/p>\n<p>        (<\/p>\n<p>         n<\/p>\n<p>          1<\/p>\n<p>          \u2212<\/p>\n<p>          c<\/p>\n<p>        )<\/p>\n<p>       O(n^{1-c})<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0641em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>\u3002\u6bcf\u4e2a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        W<\/p>\n<p>       W<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.6833em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.1389em\">W<\/span><\/span><\/span><\/span><\/span> \u4e2d\u7684\u9876\u70b9\u5b58\u50a8\u5e38\u6570\u5927\u5c0f\u7684\u4fe1\u606f\u3002\u56e0\u6b64&#xff0c;\u603b\u7a7a\u95f4\u4e3a <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>        O<\/p>\n<p>        (<\/p>\n<p>         n<\/p>\n<p>          1<\/p>\n<p>          \u2212<\/p>\n<p>          c<\/p>\n<p>        )<\/p>\n<p>       O(n^{1-c})<\/p>\n<p>    <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.0641em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\" style=\"margin-right: 0.0278em\">O<\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8141em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mathnormal mtight\">c<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c;\u6ee1\u8db3\u6b21\u7ebf\u6027\u8981\u6c42\u3002<\/p>\n<h3>\u56db\u3001 \u7406\u8bba\u610f\u4e49\u4e0e\u5f71\u54cd<\/h3>\n<li>\u5706\u6ee1\u7684\u7ec8\u70b9&#xff1a;\u672c\u6587\u7ed9\u51fa\u4e86\u5355\u904d\u6d41\u5f0fMaxDiCut\u95ee\u9898\u8fd1\u4f3c\u6bd4\u7684\u6700\u7ec8\u7b54\u6848\u2014\u2014<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         (<\/p>\n<p>          1<\/p>\n<p>          2<\/p>\n<p>         \u2212<\/p>\n<p>         \u03b5<\/p>\n<p>         )<\/p>\n<p>        (\\\\frac{1}{2}-\\\\varepsilon)<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1.1901em;vertical-align: -0.345em\"><\/span><span class=\"mopen\">(<\/span><span class=\"mord\"><span class=\"mopen nulldelimiter\"><\/span><span class=\"mfrac\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.8451em\"><span class=\"\" style=\"top: -2.655em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">2<\/span><\/span><\/span><\/span><span class=\"\" style=\"top: -3.23em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"frac-line\" style=\"border-bottom-width: 0.04em\"><\/span><\/span><span class=\"\" style=\"top: -3.394em\"><span class=\"pstrut\" style=\"height: 3em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.345em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><span class=\"mclose nulldelimiter\"><\/span><\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><span class=\"mbin\">\u2212<\/span><span class=\"mspace\" style=\"margin-right: 0.2222em\"><\/span><\/span><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord mathnormal\">\u03b5<\/span><span class=\"mclose\">)<\/span><\/span><\/span><\/span><\/span>&#xff0c; \u5e76\u4e0e\u5df2\u77e5\u4e0b\u754c\u5339\u914d\u3002\u8fd9\u6807\u5fd7\u7740\u4e00\u4e2a\u6301\u7eed\u8fd1\u5341\u5e74\u7684\u57fa\u7840\u6027\u6d41\u5f0f\u95ee\u9898\u7684\u843d\u5e55\u3002<\/li>\n<li>\u6280\u672f\u5de5\u5177\u7bb1\u7684\u4e30\u5bcc&#xff1a;\u8bba\u6587\u53d1\u5c55\u51fa\u7684\u57fa\u4e8e\u989c\u8272\u6392\u5e8f\u7684\u9012\u5f52\u6811\u7a00\u758f\u5316\u6280\u672f&#xff0c;\u4ee5\u53ca\u5904\u7406\u9ad8\u3001\u4f4e\u5ea6\u9876\u70b9\u6df7\u5408\u6a21\u578b\u4e2d\u76f8\u5173\u6027\u4f20\u64ad\u7684\u5206\u6790\u65b9\u6cd5&#xff0c;\u5177\u6709\u9ad8\u5ea6\u7684\u521b\u65b0\u6027\u548c\u901a\u7528\u6027\u3002\u8fd9\u5957\u65b9\u6cd5\u8bba\u5f88\u53ef\u80fd\u5728\u672a\u6765\u88ab\u5e94\u7528\u4e8e\u7814\u7a76\u5176\u4ed6\u66f4\u590d\u6742\u7684\u7ea6\u675f\u6ee1\u8db3\u95ee\u9898&#xff08;CSP&#xff09;\u7684\u6d41\u5f0f\u7b97\u6cd5\u3002<\/li>\n<li>\u79fb\u9664\u5173\u952e\u5047\u8bbe&#xff1a;\u6700\u5927\u7684\u8d21\u732e\u5728\u4e8e\u5f7b\u5e95\u79fb\u9664\u4e86\u201c\u5e38\u6570\u5ea6\u56fe\u201d\u8fd9\u4e00\u5f3a\u5047\u8bbe&#xff0c;\u8bc1\u660e\u4e86\u5373\u4f7f\u5728\u6700\u4e00\u822c\u7684\u56fe\u6a21\u578b\u4e0b&#xff0c;<span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>         1<\/p>\n<p>         \/<\/p>\n<p>         2<\/p>\n<p>        1\/2<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/2<\/span><\/span><\/span><\/span><\/span>\u8fd1\u4f3c\u4e5f\u662f\u53ef\u8fbe\u7684\u3002\u8fd9\u6781\u5927\u5730\u589e\u5f3a\u4e86\u7406\u8bba\u7ed3\u679c\u7684\u666e\u9002\u6027\u548c\u5b9e\u7528\u6027\u3002<\/li>\n<li>\u72ec\u7acb\u5de5\u4f5c\u7684\u5370\u8bc1&#xff1a;\u8bba\u6587\u63d0\u5230&#xff0c; Velusamy\u5728\u4e00\u7bc7\u72ec\u7acb\u5e76\u884c\u7684\u540c\u671f\u5de5\u4f5c\u4e2d&#xff0c;\u7528\u4e24\u904d\u6d41\u548c <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\">\n<p>          n<\/p>\n<p>           1<\/p>\n<p>           \u2212<\/p>\n<p>            \u03a9<\/p>\n<p>            \u03b5<\/p>\n<p>           (<\/p>\n<p>           1<\/p>\n<p>           )<\/p>\n<p>        n^{1-\\\\Omega_{\\\\varepsilon}(1)}<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 0.888em\"><\/span><span class=\"mord\"><span class=\"mord mathnormal\">n<\/span><span class=\"msupsub\"><span class=\"vlist-t\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.888em\"><span class=\"\" style=\"top: -3.063em;margin-right: 0.05em\"><span class=\"pstrut\" style=\"height: 2.7em\"><\/span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\"><span class=\"mord mtight\">1<\/span><span class=\"mbin mtight\">\u2212<\/span><span class=\"mord mtight\"><span class=\"mord mtight\">\u03a9<\/span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.1645em\"><span class=\"\" style=\"top: -2.357em;margin-left: 0em;margin-right: 0.0714em\"><span class=\"pstrut\" style=\"height: 2.5em\"><\/span><span class=\"sizing reset-size3 size1 mtight\"><span class=\"mord mtight\"><span class=\"mord mathnormal mtight\">\u03b5<\/span><\/span><\/span><\/span><\/span><span class=\"vlist-s\">\u200b<\/span><\/span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height: 0.143em\"><span class=\"\"><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"mopen mtight\">(<\/span><span class=\"mord mtight\">1<\/span><span class=\"mclose mtight\">)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> \u7a7a\u95f4\u4e5f\u8fbe\u5230\u4e86\u76f8\u540c\u7684\u8fd1\u4f3c\u6bd4\u3002\u800c\u672c\u6587\u7684\u7b97\u6cd5\u662f\u5355\u904d\u7684\u3002\u8fd9\u4e24\u9879\u5de5\u4f5c\u7684\u540c\u65f6\u51fa\u73b0&#xff0c;\u4ea4\u53c9\u5370\u8bc1\u4e86 <span class=\"katex--inline\"><span class=\"katex\"><span class=\"katex-mathml\"><\/p>\n<p>         1<\/p>\n<p>         \/<\/p>\n<p>         2<\/p>\n<p>        1\/2<\/p>\n<p>     <\/span><span class=\"katex-html\"><span class=\"base\"><span class=\"strut\" style=\"height: 1em;vertical-align: -0.25em\"><\/span><span class=\"mord\">1\/2<\/span><\/span><\/span><\/span><\/span> \u8fd1\u4f3c\u5728\u6b21\u7ebf\u6027\u7a7a\u95f4\u4e0b\u7684\u53ef\u884c\u6027&#xff0c;\u4f7f\u5f97\u7ed3\u8bba\u66f4\u52a0\u575a\u5b9e\u53ef\u9760\u3002<\/li>\n<h3>\u4e94\u3001 \u603b\u7ed3\u4e0e\u63a8\u8350<\/h3>\n<p>\u300aHalf-Approximating Maximum Dicut in the Streaming Setting\u300b\u662f\u4e00\u7bc7\u7406\u8bba\u6df1\u539a\u3001\u6280\u672f\u8270\u6df1\u4f46\u7ed3\u6784\u4f18\u7f8e\u7684\u5178\u8303\u4e4b\u4f5c\u3002\u5b83\u4e0d\u4ec5\u4ec5\u662f\u4e00\u4e2a\u5177\u4f53\u95ee\u9898\u7684\u89e3\u51b3&#xff0c;\u66f4\u662f\u6d41\u5f0f\u7b97\u6cd5\u8bbe\u8ba1\u827a\u672f\u7684\u4e00\u6b21\u7cbe\u5f69\u5c55\u793a\u3002\u9762\u5bf9\u201c\u9012\u5f52\u6811\u8fc7\u5927\u201d\u8fd9\u4e00\u6838\u5fc3\u969c\u788d&#xff0c;\u4f5c\u8005\u6ca1\u6709\u8bd5\u56fe\u86ee\u529b\u5b58\u50a8&#xff0c;\u800c\u662f\u901a\u8fc7\u5de7\u5999\u7684\u91c7\u6837&#xff08;\u7a00\u758f\u5316&#xff09;\u548c\u4f30\u8ba1&#xff08;Horvitz-Thompson&#xff09;&#xff0c;\u5c06\u95ee\u9898\u8f6c\u5316\u4e3a\u5bf9\u76f8\u5173\u6027\u7684\u7cbe\u5bc6\u63a7\u5236\u3002\u8fd9\u79cd\u201c\u4ee5\u5de7\u7834\u529b\u201d\u7684\u601d\u60f3&#xff0c;\u5bf9\u4e8e\u4ece\u4e8b\u7b97\u6cd5\u8bbe\u8ba1&#xff0c;\u5c24\u5176\u662f\u9762\u5bf9\u5927\u6570\u636e\u8ba1\u7b97\u7ea6\u675f\u7684\u7814\u7a76\u8005\u800c\u8a00&#xff0c;\u6781\u5177\u542f\u53d1\u6027\u3002<\/p>\n<p>\u63a8\u8350\u8bfb\u8005&#xff1a;<\/p>\n<ul>\n<li>\u6d41\u5f0f\u7b97\u6cd5\u9886\u57df\u7684\u7814\u7a76\u8005&#xff1a;\u672c\u6587\u662f\u5fc5\u8bfb\u7684\u7ecf\u5178&#xff0c;\u5176\u6280\u672f\u7ec6\u8282\u503c\u5f97\u53cd\u590d\u94bb\u7814\u3002<\/li>\n<li>\u7406\u8bba\u8ba1\u7b97\u673a\u79d1\u5b66\u7684\u5b66\u751f&#xff1a;\u53ef\u4ee5\u901a\u8fc7\u672c\u6587\u5b66\u4e60\u5982\u4f55\u5c06\u79bb\u7ebf\u7b97\u6cd5\u975e\u5e73\u51e1\u5730\u9002\u914d\u5230\u6d41\u5f0f\u6a21\u578b&#xff0c;\u4ee5\u53ca\u5982\u4f55\u5904\u7406\u590d\u6742\u7684\u6982\u7387\u5206\u6790\u548c\u76f8\u5173\u6027\u3002<\/li>\n<li>\u5bf9\u5927\u6570\u636e\u8fd1\u4f3c\u7b97\u6cd5\u611f\u5174\u8da3\u7684\u5de5\u7a0b\u5e08&#xff1a;\u5c3d\u7ba1\u7406\u8bba\u6027\u5f3a&#xff0c;\u4f46\u5176\u201c\u91c7\u6837-\u4f30\u8ba1\u201d\u7684\u6838\u5fc3\u8303\u5f0f\u5728\u5b9e\u9645\u7684\u5927\u89c4\u6a21\u56fe\u5904\u7406\u7cfb\u7edf\u4e2d\u6709\u7740\u5e7f\u6cdb\u7684\u5e94\u7528\u524d\u666f\u3002<\/li>\n<\/ul>\n<p>\u603b\u800c\u8a00\u4e4b&#xff0c;\u8fd9\u7bc7\u8bba\u6587\u50cf\u4e00\u4f4d\u6280\u827a\u9ad8\u8d85\u7684\u5de5\u5320&#xff0c;\u7528\u7cbe\u5bc6\u7684\u5de5\u5177\u548c\u4e25\u8c28\u7684\u63a8\u7406&#xff0c;\u5728\u6d41\u5f0f\u7b97\u6cd5\u7684\u6bbf\u5802\u91cc&#xff0c;\u4e3aMaxDiCut\u95ee\u9898\u9576\u5d4c\u4e0a\u4e86\u6700\u540e\u4e00\u5757&#xff0c;\u4e5f\u662f\u6700\u5b8c\u7f8e\u7684\u4e00\u5757\u7816\u3002\u5b83\u544a\u8bc9\u6211\u4eec&#xff0c;\u5373\u4f7f\u5728\u5927\u6570\u636e\u6d41\u7684\u91cd\u91cd\u9650\u5236\u4e0b&#xff0c;\u901a\u8fc7\u6df1\u523b\u7684\u6d1e\u5bdf\u548c\u7cbe\u5de7\u7684\u8bbe\u8ba1&#xff0c;\u6211\u4eec\u4f9d\u7136\u80fd\u591f\u65e0\u9650\u903c\u8fd1\u8ba1\u7b97\u7684\u7406\u8bba\u6781\u9650\u3002<\/p>\n<hr \/>\n<h4>&#x1f4da; \u53c2\u8003\u8d44\u6599<\/h4>\n<ul>\n<li>\u8bba\u6587\u94fe\u63a5&#xff1a;\u70b9\u51fb\u67e5\u770b\u539f\u8bba\u6587 \u66f4\u591a\u7ec6\u8282&#xff0c;\u53ef\u70b9\u51fb\u67e5\u770b\u539f\u8bba\u6587\u3002<\/li>\n<\/ul>\n<hr \/>\n<p>\u4ee5\u4e0a\u5c31\u662f\u5bf9\u672c\u8bba\u6587\u7684\u5168\u9762\u5206\u4eab\u3002\u5982\u679c\u4f60\u5bf9\u67d0\u4e2a\u7ec6\u8282\u611f\u5174\u8da3&#xff0c;\u6b22\u8fce\u7559\u8a00\u8ba8\u8bba&#xff0c;\u6211\u4f1a\u8fdb\u4e00\u6b65\u6df1\u5165\u89e3\u8bfb&#xff01;&#x1f468;\u200d&#x1f4bb;&#x1f469;\u200d&#x1f4bb;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5728\u5f53\u4eca\u5927\u6570\u636e\u65f6\u4ee3&#xff0c;\u6570\u636e\u5e38\u4ee5\u9ad8\u901f\u201c\u6d41\u201d\u7684\u5f62\u5f0f\u6c79\u6d8c\u800c\u81f3&#xff0c;\u65e0\u6cd5\u88ab\u5b8c\u6574\u5b58\u50a8\u3002\u6d41\u5f0f\u7b97\u6cd5&#xff08;Streaming Algorithm&#xff09;\u5e94\u8fd0\u800c\u751f&#xff0c;\u5b83\u8981\u6c42\u4ec5\u7528\u5355\u904d\u6216\u5c11\u6570\u51e0\u904d\u626b\u63cf\u6570\u636e&#xff0c;\u4e14\u4f7f\u7528\u8fdc\u5c0f\u4e8e\u6570\u636e\u603b\u91cf\u7684\u5185\u5b58&#xff08;\u5373\u6b21\u7ebf\u6027\u7a7a\u95f4&#xff09;\u6765\u5b8c\u6210\u8ba1\u7b97\u4efb\u52a1\u3002\u8fd9\u79cd\u6a21\u578b\u5bf9\u4e8e\u5904\u7406\u8d85\u5927\u89c4\u6a21\u56fe\u6570\u636e\u5c24\u4e3a\u91cd\u8981\u3002\u5176\u4e2d&#xff0c;\u6700\u5927\u6709\u5411\u5272&#xff08;Maximum Directed Cut&#xff0c; Ma<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[6263,6261,6258,6259,6257,6262,6260],"topic":[],"class_list":["post-59370","post","type-post","status-publish","format-standard","hentry","category-server","tag-6263","tag-6261","tag-6258","tag-6259","tag-6257","tag-6262","tag-6260"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v20.3 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/59370.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u5728\u5f53\u4eca\u5927\u6570\u636e\u65f6\u4ee3&#xff0c;\u6570\u636e\u5e38\u4ee5\u9ad8\u901f\u201c\u6d41\u201d\u7684\u5f62\u5f0f\u6c79\u6d8c\u800c\u81f3&#xff0c;\u65e0\u6cd5\u88ab\u5b8c\u6574\u5b58\u50a8\u3002\u6d41\u5f0f\u7b97\u6cd5&#xff08;Streaming Algorithm&#xff09;\u5e94\u8fd0\u800c\u751f&#xff0c;\u5b83\u8981\u6c42\u4ec5\u7528\u5355\u904d\u6216\u5c11\u6570\u51e0\u904d\u626b\u63cf\u6570\u636e&#xff0c;\u4e14\u4f7f\u7528\u8fdc\u5c0f\u4e8e\u6570\u636e\u603b\u91cf\u7684\u5185\u5b58&#xff08;\u5373\u6b21\u7ebf\u6027\u7a7a\u95f4&#xff09;\u6765\u5b8c\u6210\u8ba1\u7b97\u4efb\u52a1\u3002\u8fd9\u79cd\u6a21\u578b\u5bf9\u4e8e\u5904\u7406\u8d85\u5927\u89c4\u6a21\u56fe\u6570\u636e\u5c24\u4e3a\u91cd\u8981\u3002\u5176\u4e2d&#xff0c;\u6700\u5927\u6709\u5411\u5272&#xff08;Maximum Directed Cut&#xff0c; Ma\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/59370.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2026-01-13T11:17:09+00:00\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/59370.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/59370.html\",\"name\":\"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2026-01-13T11:17:09+00:00\",\"dateModified\":\"2026-01-13T11:17:09+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/59370.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/59370.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/59370.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/59370.html","og_locale":"zh_CN","og_type":"article","og_title":"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u5728\u5f53\u4eca\u5927\u6570\u636e\u65f6\u4ee3&#xff0c;\u6570\u636e\u5e38\u4ee5\u9ad8\u901f\u201c\u6d41\u201d\u7684\u5f62\u5f0f\u6c79\u6d8c\u800c\u81f3&#xff0c;\u65e0\u6cd5\u88ab\u5b8c\u6574\u5b58\u50a8\u3002\u6d41\u5f0f\u7b97\u6cd5&#xff08;Streaming Algorithm&#xff09;\u5e94\u8fd0\u800c\u751f&#xff0c;\u5b83\u8981\u6c42\u4ec5\u7528\u5355\u904d\u6216\u5c11\u6570\u51e0\u904d\u626b\u63cf\u6570\u636e&#xff0c;\u4e14\u4f7f\u7528\u8fdc\u5c0f\u4e8e\u6570\u636e\u603b\u91cf\u7684\u5185\u5b58&#xff08;\u5373\u6b21\u7ebf\u6027\u7a7a\u95f4&#xff09;\u6765\u5b8c\u6210\u8ba1\u7b97\u4efb\u52a1\u3002\u8fd9\u79cd\u6a21\u578b\u5bf9\u4e8e\u5904\u7406\u8d85\u5927\u89c4\u6a21\u56fe\u6570\u636e\u5c24\u4e3a\u91cd\u8981\u3002\u5176\u4e2d&#xff0c;\u6700\u5927\u6709\u5411\u5272&#xff08;Maximum Directed Cut&#xff0c; Ma","og_url":"https:\/\/www.wsisp.com\/helps\/59370.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2026-01-13T11:17:09+00:00","author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"7 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/59370.html","url":"https:\/\/www.wsisp.com\/helps\/59370.html","name":"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834 - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2026-01-13T11:17:09+00:00","dateModified":"2026-01-13T11:17:09+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/59370.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/59370.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/59370.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u8bba\u6587\u5206\u4eab\u4e0e\u89e3\u6790\uff5c\u903c\u8fd1\u6781\u9650\uff1a\u5355\u904d\u6d41\u5f0f\u7b97\u6cd5\u4e2d\u6700\u5927\u6709\u5411\u5272\u76841\/2\u8fd1\u4f3c\u6bd4\u7a81\u7834"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/59370","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=59370"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/59370\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=59370"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=59370"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=59370"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=59370"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}