{"id":82,"date":"2026-03-21T20:10:35","date_gmt":"2026-03-21T12:10:35","guid":{"rendered":"http:\/\/www.chenwenhao.xyz\/?p=82"},"modified":"2026-03-21T20:14:18","modified_gmt":"2026-03-21T12:14:18","slug":"%e6%97%b6%e9%97%b4%e5%a4%8d%e6%9d%82%e5%ba%a6%e7%9a%84%e8%ae%a1%e7%ae%97","status":"publish","type":"post","link":"https:\/\/www.chenwenhao.xyz\/index.php\/2026\/03\/21\/%e6%97%b6%e9%97%b4%e5%a4%8d%e6%9d%82%e5%ba%a6%e7%9a%84%e8%ae%a1%e7%ae%97\/","title":{"rendered":"\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u8ba1\u7b97"},"content":{"rendered":"\n

\u4e00 \u6982\u5ff5<\/h2>\n\n\n\n

\u65f6\u95f4\u590d\u6742\u5ea6\u63cf\u8ff0\u7b97\u6cd5\u6267\u884c\u65f6\u95f4\u968f\u95ee\u9898\u89c4\u6a21n\u589e\u5927\u800c\u53d8\u5316\u7684\u8d8b\u52bf,\u662f\u5173\u4e8en\u7684\u6e10\u8fd1\u51fd\u6570\u3002<\/strong>\u7b97\u6cd5\u6267\u884c\u65f6\u95f4\u901a\u5e38\u7531\u8bed\u53e5\u9891\u5ea6(\u67d0\u6761\u8bed\u53e5\u7684\u6267\u884c\u6b21\u6570)\u6765\u8861\u91cf\u3002\u8bbe\u7b97\u6cd5\u4e2d\u6240\u6709\u8bed\u53e5\u7684\u9891\u5ea6\u4e4b\u548c\u4e3aT(n),\u5b83\u662f\u95ee\u9898\u89c4\u6a21n\u7684\u51fd\u6570\u3002\u5f53n\u8db3\u591f\u5927\u65f6,\u4f4e\u9636\u9879\u548c\u5e38\u6570\u7cfb\u6570\u5bf9\u6574\u4f53\u589e\u957f\u8d8b\u52bf\u7684\u5f71\u54cd\u53ef\u4ee5\u5ffd\u7565\u4e0d\u8ba1,\u56e0\u6b64\u53ea\u9700\u5173\u6ce8T(n)\u4e2d\u589e\u957f\u6700\u5feb\u7684\u9879\u3002\u8fd9\u4e00\u9879\u901a\u5e38\u7531\u7b97\u6cd5\u4e2d\u7684\u57fa\u672c\u8fd0\u7b97(\u5173\u952e\u8bed\u53e5)\u7684\u6267\u884c\u6b21\u6570\u51b3\u5b9a,\u8be5\u6267\u884c\u6b21\u6570\u7684\u6570\u91cf\u7ea7\u5373\u4e3a\u6574\u4e2a\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n

\u65f6\u95f4\u590d\u6742\u5ea6\u901a\u5e38\u7528\u5927O\u8bb0\u53f7\u8868\u793a:\u82e5\u5b58\u5728\u6b63\u5e38\u6570C\u548cn0<\/sub>\uff0c\u4f7f\u5f97\u5bf9\u6240\u6709n\u2265n0<\/sub>\u65f6,\u90fd\u67090<\/mn>\u2264<\/mo>T<\/mi>(<\/mo>n<\/mi>)<\/mo>\u2264<\/mo>C<\/mi>f<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>0 \\leq T(n) \\leq C f(n)<\/annotation><\/semantics><\/math>\uff0c\u5219\u79f0T(n)=O(f(n))\uff0c\u5b83\u8868\u793a\u5f53n\u8db3\u591f\u5927\u65f6,T(n)\u7684\u589e\u957f\u901f\u5ea6\u4e0d\u8d85\u8fc7f(n)\u7684\u5e38\u6570\u500d\u3002<\/p>\n\n\n\n

e.g\uff1aT<\/mi>(<\/mo>n<\/mi>)<\/mo>=<\/mo>3<\/mn>n<\/mi>2<\/mn><\/msup>+<\/mo>100<\/mn>n<\/mi>+<\/mo>5<\/mn>\u2192<\/mo>O<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>T(n) = 3n^2 + 100n + 5 \\to O(n^2)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n

\u4e8c \u52a0\u6cd5\u539f\u5219\u4e0e\u4e58\u6cd5\u539f\u5219<\/h2>\n\n\n\n

2.1 \u52a0\u6cd5\u539f\u5219<\/h4>\n\n\n\n

\u5982\u679c\u4e24\u6bb5\u4ee3\u7801\u6309\u987a\u5e8f\u6267\u884c\uff0c\u5219\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a\u4e24\u8005\u4e2d\u7684\u9ad8\u9636\u9879\uff0c\u5224\u65ad\u65b9\u6cd5\u770b\u9636\u6b21<\/p>\n\n\n\n

\u5373\uff1aO<\/mi>(<\/mo>f<\/mi>(<\/mo>n<\/mi>)<\/mo>)<\/mo>+<\/mo>O<\/mi>(<\/mo>g<\/mi>(<\/mo>n<\/mi>)<\/mo>)<\/mo>=<\/mo>O<\/mi>(<\/mo>max<\/mi>\u2061<\/mo><\/mrow>{<\/mo>f<\/mi>(<\/mo>n<\/mi>)<\/mo>,<\/mo>g<\/mi>(<\/mo>n<\/mi>)<\/mo>}<\/mo>)<\/mo><\/mrow>O(f(n)) + O(g(n)) = O(\\max\\{f(n), g(n)\\})<\/annotation><\/semantics><\/math><\/p>\n\n\n\n

e.g:<\/p>\n\n\n\n

void example1(int n) {\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < n; j++) {\n            printf(\"%d \", i + j);\n        }\n    }\/\/\u7b2c\u4e00\u6bb5\n    for (int k = 0; k < n; k++) {\n        printf(\"%d \", k);\n    }\n}\/\/\u7b2c\u4e8c\u6bb5<\/code><\/pre>\n\n\n\n
\u5176\u4e2d\uff0c\u7b2c\u4e00\u6bb5\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>O(n^2)<\/annotation><\/semantics><\/math>\uff0c\u7b2c\u4e8c\u6bb5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math>\uff0c\u5219O<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo>+<\/mo>O<\/mi>(<\/mo>n<\/mi>)<\/mo>=<\/mo>O<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>O(n^2)+O(n)=O(n^2)<\/annotation><\/semantics><\/math>\uff0c\u6545\u8fd9\u4e2aexample1\u51fd\u6570\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>O(n^2)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
2.2 \u4e58\u6cd5\u539f\u5219<\/h4>\n\n\n\n
\u5982\u679c\u6709\u4e00\u6bb5\u4ee3\u7801\u5d4c\u5957\u5728\u53e6\u4e00\u6bb5\u7684\u5185\u90e8\uff0c\u5219\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a\u4e24\u8005\u4e58\u79ef<\/p>\n\n\n\n
\u5373\uff1aO<\/mi>(<\/mo>f<\/mi>(<\/mo>n<\/mi>)<\/mo>)<\/mo>\u22c5<\/mo>O<\/mi>(<\/mo>g<\/mi>(<\/mo>n<\/mi>)<\/mo>)<\/mo>=<\/mo>O<\/mi>(<\/mo>f<\/mi>(<\/mo>n<\/mi>)<\/mo>\u22c5<\/mo>g<\/mi>(<\/mo>n<\/mi>)<\/mo>)<\/mo><\/mrow>O(f(n)) \\cdot O(g(n)) = O(f(n) \\cdot g(n))<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
e.g<\/p>\n\n\n\n
void demo(int n) {\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < n; j++) {\n            printf(\"%d \", i + j);\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
\u5176\u4e2d\uff0c\u5916\u5c42\u5faa\u73af\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n)\uff0c\u5185\u5c42\u5faa\u73af\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math>\uff0c\u6839\u636e\u4e58\u6cd5\u539f\u5219\uff0c\u8fd9\u6bb5\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>)<\/mo>\u22c5<\/mo>O<\/mi>(<\/mo>n<\/mi>)<\/mo>=<\/mo>O<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>O(n)\\cdot O(n)=O(n^2)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
\u4e09 \u65f6\u95f4\u590d\u6742\u5ea6\u7684\u9636\u6b21<\/h2>\n\n\n\n
O<\/mi>(<\/mo>1<\/mn>)<\/mo><<\/mo>O<\/mi>(<\/mo>log<\/mi>2<\/mn><\/msub>\u2061<\/mo><\/mspace>n<\/mi>)<\/mo><<\/mo>O<\/mi>(<\/mo>n<\/mi>)<\/mo><<\/mo>O<\/mi>(<\/mo>n<\/mi><\/mspace>log<\/mi>2<\/mn><\/msub>\u2061<\/mo><\/mspace>n<\/mi>)<\/mo><<\/mo>O<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><<\/mo>O<\/mi>(<\/mo>n<\/mi>k<\/mi><\/msup>)<\/mo><<\/mo>O<\/mi>(<\/mo>2<\/mn>n<\/mi><\/msup>)<\/mo><<\/mo>O<\/mi>(<\/mo>n<\/mi>!<\/mo>)<\/mo><<\/mo>O<\/mi>(<\/mo>n<\/mi>n<\/mi><\/msup>)<\/mo><\/mrow>O(1) < O(\\log_2 n) < O(n) < O(n \\log_2 n) < O(n^2) < O(n^k) < O(2^n) < O(n!) < O(n^n)\n<\/annotation><\/semantics><\/math><\/div>\n\n\n\n
\u6839\u636e\u8fd9\u4e2a\uff0c\u5728\u52a0\u6cd5\u539f\u5219\u4e2d\uff0c\u5c31\u53ef\u4ee5\u5224\u65ad\u54ea\u4e2a\u9636\u6b21\u9ad8\uff0c\u4ece\u800c\u89e3\u51fa\u6b63\u786e\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
\u56db \u65f6\u95f4\u590d\u6742\u5ea6\u7684\u6c42\u6cd5<\/h2>\n\n\n\n
4.1 \u666e\u901a\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/h4>\n\n\n\n
e.g<\/p>\n\n\n\n
void func(int n) {\n    int a = 10;\n    int b = 20;\n    int c = a + b;\n}\n<\/code><\/pre>\n\n\n\n
\u8fd9\u6bb5\u4ee3\u7801\u91cc\u9762\u672a\u5305\u542b\u4efb\u4f55\u5faa\u73af\uff0c\u6545\u5176\u65f6\u95f4\u590d\u6742\u5ea6\u5fc5\u7136\u4e3aO(1)<\/p>\n\n\n\n
4.2 while\u5faa\u73af\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u6c42\u6cd5<\/h4>\n\n\n\n
\u5bf9\u4e8ewhile\u5faa\u73af\u6c42\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u8bbet\u6cd5\uff0c\u5217\u51fa\u8868\u683c\u89e3\u51fat\uff0c\u5219t\u5373\u4e3a\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
t<\/td>1<\/td>2<\/td>……<\/td>t<\/td><\/tr>
x<\/td><\/td><\/td><\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
e.g<\/p>\n\n\n\n
void fun(int n) {
int i = 1;
while (i <= n) {
i = i * 2;<\/strong>\/\/\u5173\u952e\u8bed\u53e5
}
}<\/p>\n\n\n\n
\u6b64\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u8bbe\u5173\u952e\u8bed\u53e5\u8fd0\u884c\u65f6\u95f4\u4e3at\uff0c\u5373\u8bbei=i*2\u8fd0\u884c\u4e86t\u6b21\uff0c\u5219\u53ef\u4ee5\u5217\u51fa\u8868\u683c<\/p>\n\n\n\n
t<\/td>1<\/td>2<\/td>3<\/td>……<\/td>t<\/td><\/tr>
i<\/td>2<\/td>4<\/td>8<\/td>……<\/td>2<\/mn>t<\/mi><\/msup>2^{t}<\/annotation><\/semantics><\/math><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\u5f532<\/mn>t<\/mi><\/msup>><\/mo>n<\/mi><\/mrow>2^{t}>n<\/annotation><\/semantics><\/math>\u7684\u65f6\u5019\uff0c\u8df3\u51fa\u5faa\u73af\uff0c\u89e3\u5f97t>log<\/mi>2<\/mn><\/msub>\u2061<\/mo><\/mspace>n<\/mi><\/mrow>\\log_2 n<\/annotation><\/semantics><\/math>\uff0c\u6545\u8fd9\u6bb5\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>log<\/mi>2<\/mn><\/msub>\u2061<\/mo><\/mspace>n<\/mi>)<\/mo><\/mrow>O(\\log_2 n)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
4.3 for\u5faa\u73af\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u6c42\u6cd5<\/h4>\n\n\n\n
4.3.1 \u666e\u901a\u5faa\u73af<\/h5>\n\n\n\n
e.g.1<\/p>\n\n\n\n
void test(int n){\n    int x = 10;\n    for(int i=0; i<10; i++){\n        x++;\n    }\n}<\/code><\/pre>\n\n\n\n
\u6b64\u65f6n\u5c0f\u4e8e10\uff0c\u4ee3\u8868\u53ea\u4f1a\u5faa\u73af\u5341\u6b21\uff0c\u6545\u8fd9\u6bb5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(1)<\/p>\n\n\n\n
e.g.2<\/p>\n\n\n\n
void test1(int n) {\n    for (int i = 0; i < n; i++) {\n        printf(\"hello\");\n    }\n}<\/code><\/pre>\n\n\n\n
\u8fd9\u4e2a\u5faa\u73af\u4e2d\uff0ci=0\uff0c\u6545\u4f1a\u5faa\u73afn\u6b21\uff0c\u6545\u8fd9\u6bb5\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
4.3.2 \u5d4c\u5957\u5faa\u73af<\/h5>\n\n\n\n
\u5bf9\u4e8e\u5d4c\u5957\u5faa\u73af\uff0c\u4e5f\u53ef\u4ee5\u4f7f\u7528\u8868\u683c\u6cd5\uff0c\u6765\u8fdb\u884c\u89e3\u51b3\uff0c\u6700\u540e\u5bf9\u5185\u5faa\u73af\u6b21\u76ee\u8fdb\u884c\u6c42\u548c\u5373\u53ef<\/p>\n\n\n\n
\u5916\u5faa\u73af\u6b21\u6570<\/td><\/td><\/tr>
\u5faa\u73af\u6761\u4ef6<\/td><\/td><\/tr>
i\u53d6\u503c<\/td><\/td><\/tr>
\u5185\u5faa\u73af\u6b21\u76ee<\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
e.g.1<\/p>\n\n\n\n
for(int i = n-1; i >= 2; i--){\n    for(int j = 1; j < i; j++){  \n        if(A[j] > A[j+1]){\n            int temp = A[j];\n            A[j] = A[j+1];\n            A[j+1] = temp;\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
\u9047\u5230\u5d4c\u5957\u5faa\u73af\uff0c\u9996\u5148\u8981\u5148\u5224\u65ad\u53d8\u91cf\u6709\u8ddf\u5faa\u73af\u6709\u76f4\u63a5\u5173\u7cfb\uff0c\u5982\u679c\u6709\uff0c\u518d\u5217\u8868\u683c<\/p>\n\n\n\n
\u8fd9\u91cc\u5f88\u660e\u663e\u6709\uff0c\u6240\u4ee5\u76f4\u63a5\u5217\u8868\u683c\u5373\u53ef<\/p>\n\n\n\n
\u5916\u5faa\u73af\u6b21\u6570<\/td>1<\/td>2<\/td>3<\/td>……<\/td>t<\/td><\/tr>
\u5faa\u73af\u6761\u4ef6<\/td>n-1<\/td>n-2<\/td>n-3<\/td>……<\/td>1<\/td><\/tr>
i\u53d6\u503c<\/td>n-1<\/td>n-2<\/td>n-3<\/td>……<\/td>1<\/td><\/tr>
\u5185\u5faa\u73af\u6b21\u76ee<\/td>n-2
(j<i,i=n-1,\u6545\u4e3an-2)<\/td>		n-3<\/td>n-4<\/td>……<\/td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\u5f53t<1\u65f6\uff0c\u5faa\u73af\u8df3\u51fa\uff0c\u6b64\u65f6\u53ef\u4ee5\u77e5\u9053\uff0ct=1\u4e3a\u6700\u540e\u4e00\u6b21\u5faa\u73af\u503c\uff0c\u90a3\u4e48\u7684\u8bdd\u5c31\u53ef\u4ee5\u5bf9\u5185\u5faa\u73af\u6b21\u76ee\u8fdb\u884c\u6c42\u548c\u4e86<\/p>\n\n\n\n
\u6b64\u65f6\u2211<\/mo>i<\/mi>=<\/mo>1<\/mn><\/mrow>n<\/mi>\u2212<\/mo>2<\/mn><\/mrow><\/msubsup>i<\/mi><\/mrow>\\sum_{i=1}^{n-2} i<\/annotation><\/semantics><\/math>=\u2211<\/mo>i<\/mi>=<\/mo>1<\/mn><\/mrow>n<\/mi>\u2212<\/mo>2<\/mn><\/mrow><\/msubsup>i<\/mi>=<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>2<\/mn>)<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>2<\/mn>+<\/mo>1<\/mn>)<\/mo><\/mrow>2<\/mn><\/mfrac>=<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>2<\/mn>)<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow>2<\/mn><\/mfrac><\/mrow>\\sum_{i=1}^{n-2} i  = \\frac{(n-2)(n-2+1)}{2}  = \\frac{(n-2)(n-1)}{2}<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
\u7531\u4e8e\u65f6\u95f4\u590d\u6742\u5ea6\u53ea\u770b\u6700\u9ad8\u9879\uff0c\u6545\u8fd9\u65f6\u5019\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u5ffd\u7565\u6389\u5176\u4ed6\u9879\u548c\u6700\u9ad8\u9879\u524d\u9762\u7684\u7cfb\u6570\uff0c\u53ea\u770b\u6700\u9ad8\u9879\uff0c\u4e3an<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>,\u6545\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n<\/mi>2<\/mn><\/msup>n^2<\/annotation><\/semantics><\/math>)<\/p>\n\n\n\n
e.g.2 <\/p>\n\n\n\n
\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
\tint count = 0;\n\tfor (int k = 1; k <= n; k *= 2) {\n\t\tfor (int j = 1; j <= n; j++) {\n\t\t\tcount++;\n\t\t}\n\t}<\/code><\/pre>\n\n\n\n
\u9996\u5148\u5148\u5224\u65ad\u5185\u5c42\u5faa\u73af\u662f\u5426\u8ddf\u5916\u5c42\u7684i\u503c\u6709\u5173\u7cfb\uff0c\u5f88\u660e\u663e\u6ca1\u6709\uff0c\u6545\u63a5\u4e0b\u6765\u76f4\u63a5\u5217\u8868\u683c\u5373\u53ef<\/p>\n\n\n\n
\u5916\u5faa\u73af\u6b21\u6570<\/td>1<\/td>2<\/td>3<\/td>……<\/td>t<\/td><\/tr>
\u5faa\u73af\u6761\u4ef6<\/td>1<\/td>2<\/td>4<\/td>……<\/td>2<\/mn>t<\/mi>\u2212<\/mo>1<\/mn><\/mrow><\/msup>2^{t-1}<\/annotation><\/semantics><\/math><\/td><\/tr>
i\u53d6\u503c<\/td>1<\/td>2<\/td>4<\/td>……<\/td>2<\/mn>t<\/mi>\u2212<\/mo>1<\/mn><\/mrow><\/msup>2^{t-1}<\/annotation><\/semantics><\/math><\/td><\/tr>
\u5185\u5faa\u73af\u6b21\u76ee<\/td>n<\/td>n<\/td>n<\/td>……<\/td>n<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\u6b64\u65f6\u5f532<\/mn>t<\/mi>\u2212<\/mo>1<\/mn><\/mrow><\/msup>><\/mo>n<\/mi><\/mrow>2^{t-1}>n<\/annotation><\/semantics><\/math>\uff0c\u5373t>log<\/mi>2<\/mn><\/msub>\u2061<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow>\\log_2 (n-1)<\/annotation><\/semantics><\/math>\uff0c\u8df3\u51fa\u5faa\u73af\uff0c\u6b64\u65f6\u5bf9\u5185\u5faa\u73af\u6b21\u76ee\u8fdb\u884c\u6c42\u548c\uff0c\u7531\u4e8e\u90fd\u662fn\uff0c\u4e00\u5171\u6709log<\/mi>2<\/mn><\/msub>\u2061<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow>\\log_2 (n-1)<\/annotation><\/semantics><\/math>\u9879\uff0c\u6240\u4ee5\u6700\u540e\u4e3anlog<\/mi>2<\/mn><\/msub>\u2061<\/mo>(<\/mo>n<\/mi>\u2212<\/mo>1<\/mn>)<\/mo><\/mrow>\\log_2 (n-1)<\/annotation><\/semantics><\/math>=n<\/mi><\/mspace>log<\/mi>2<\/mn><\/msub>\u2061<\/mo><\/mspace>n<\/mi><\/mrow>n\\log_2 n<\/annotation><\/semantics><\/math>–n<\/mi>n<\/annotation><\/semantics><\/math>\uff0c\u6839\u636e\u52a0\u6cd5\u539f\u7406\uff0c\u6545\u6700\u540e\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi><\/mspace>log<\/mi>2<\/mn><\/msub>\u2061<\/mo><\/mspace>n<\/mi>)<\/mo><\/mrow>O(n\\log_2 n)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
\u4e94 \u738b\u9053\u4e66\u65f6\u95f4\u590d\u6742\u5ea6\u7ec3\u4e60\u89e3\u7b54<\/h2>\n\n\n\n
\u8fd9\u4e00\u6bb5\u5c06\u4e3a\u738b\u9053\u4e66\u4e0a\u65f6\u95f4\u590d\u6742\u5ea6\u90a3\u5757\u8fdb\u884c\u89e3\u6790<\/p>\n\n\n\n
7. <\/p>\n\n\n\n
\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
void fun(int n) {\n    int i = 0;\n    while (i * i * i <= n)\n        i++;\n}<\/code><\/pre>\n\n\n\n
\u8fd9\u4e00\u9898\u8003\u7684\u662fwhile\u5faa\u73af\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6c42\u6cd5\uff0c\u5229\u7528\u8bbet\u6cd5\u6765\u89e3\u5c31\u53ef\u4ee5\u4e86<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
9.\u6c42\u4e0b\u5217\u4ee3\u7801\u6bb5\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
if (n >= 0) {\n    for (int i = 0; i < n; i++)\n        for (int j = 0; j < n; j++)\n            printf(\"\u8f93\u5165\u6570\u636e\u5927\u4e8e\u6216\u7b49\u4e8e\u96f6\\n\");\n} else {\n    for (int j = 0; j < n; j++)\n        printf(\"\u8f93\u5165\u6570\u636e\u5c0f\u4e8e\u96f6\\n\");\n}<\/code><\/pre>\n\n\n\n
\u8fd9\u9898\u8003\u7684\u662f\u5d4c\u5957for\u5faa\u73af\u548c\u52a0\u6cd5\u539f\u7406\uff0c\u7b2c\u4e00\u4e2a\u5f88\u660e\u663e\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>O(n^2)<\/annotation><\/semantics><\/math>,\u4e0b\u9762\u8fd9\u4e2a\u5f88\u660e\u663e\u662fO<\/mi>(<\/mo>n<\/mi>)<\/mo><\/mrow>O(n)<\/annotation><\/semantics><\/math>,\u90a3\u4e48\u5229\u7528\u52a0\u6cd5\u539f\u7406\u5c31\u53ef\u4ee5\u77e5\u9053\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO<\/mi>(<\/mo>n<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow>O(n^2)<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
10.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u8fd0\u884c\u6b21\u6570<\/p>\n\n\n\n
int m = 0, i, j;\nfor (i = 1; i <= n; i++)\n    for (j = 1; j <= 2 * i; j++)\n        m++; <\/code><\/pre>\n\n\n\n
\u6ce8\u610f\u5230\u5b83\u8003\u7684\u662f\u8fd0\u884c\u6b21\u6570\uff0c\u90a3\u4e48\u7684\u8bdd\u53ea\u9700\u8981\u628a\u6700\u540e\u7684\u6c42\u548c\u7ed9\u6c42\u51fa\u6765\u5c31\u53ef\u4ee5\u4e86<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
11.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
int Func(int n) {\n    if (n == 1)\n        return 1;\n    else\n        return 2 * Func(n \/ 2) + n;\n}<\/code><\/pre>\n\n\n\n
\u8fd9\u9053\u9898\u8003\u5230\u4e86\u4e00\u4e2a\u9012\u5f52\u51fd\u6570\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u6c42\u6cd5\uff0c\u5bf9\u4e8e\u8fd9\u7c7b\u9898\uff0c\u5173\u6ce8\u5b83\u7684\u5173\u952e\u8bed\u53e5\u5c31\u53ef\u4ee5\u4e86\uff0c\u6ce8\u610f\u5230\u4e00\u4e2a\u662fn<\/mi>\/<\/mi>2<\/mn><\/mrow>n\/2<\/annotation><\/semantics><\/math>\uff0c\u90a3\u4e48\u540e\u9762\u5c31\u662f\u5bf9n\u8fdb\u884c\u4e00\u4e2a\u8d4b\u503c\uff0c\u6545\u6211\u4eec\u5c31\u53ef\u4ee5\u628a\u8fd9\u4e2a\u8bed\u53e5\u8f6c\u6362\u4e3an=(n\/2)\u8fdb\u884c\u4e00\u4e2a\u5faa\u73af\uff0c\u5229\u7528\u8bbet\u6cd5\u6765\u89e3\u5373\u53ef<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
12.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
x = 2;\nwhile (x < n \/ 2)\n    x = 2 * x;<\/code><\/pre>\n\n\n\n
\u8fd9\u4e2a\u7684\u8bdd\u76f4\u63a5\u7528\u8bbet\u6cd5\u6765\u89e3\u5c31\u53ef\u4ee5\u4e86<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
13.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
int fact(int n) {\n    if (n <= 1)\n        return 1;\n    return n * fact(n - 1);\n}<\/code><\/pre>\n\n\n\n
\u8fd8\u662f\u9012\u5f52\u51fd\u6570\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u627e\u5230\u5173\u952e\u8bed\u53e5\uff0c\u6ce8\u610f\u5230\u662f\u628an\u53d8\u6210n-1\uff0c\u90a3\u4e48\u8fd9\u4e2a\u8bed\u53e5\u5c31\u53ef\u4ee5\u53d8\u6210n=n-1\uff0c\u8f6c\u6362\u6210\u4e00\u4e2awhile\u5faa\u73af\uff0c\u5373\u53ef\u6c42\u51fa\u7b54\u6848<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
15.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff082017\u5e74\u7edf\u8003\u771f\u9898\uff09<\/p>\n\n\n\n
int func(int n) {\n    int i = 0, sum = 0;\n    while (sum < n)\n        sum += ++i;\n    return i;\n}<\/code><\/pre>\n\n\n\n
\u8fd9\u4e5f\u662f\u4e00\u4e2awhile\u5faa\u73af\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u7528\u8bbet\u6cd5\u5c31\u53ef\u4ee5\u89e3\u51b3\u4e86<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
16.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff082019\u5e74\u7edf\u8003\u771f\u9898\uff09<\/p>\n\n\n\n
x = 0;\nwhile (n >= (x + 1) * (x + 1))\n    x = x + 1;<\/code><\/pre>\n\n\n\n
\u8fd8\u662f\u7528\u8bbet\u6cd5\u5373\u53ef\u8fc5\u901f\u89e3\u51b3<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
17.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
int sum = 0;\nfor (int i = 1; i < n; i *= 2)\n    for (int j = 0; j < i; j++)\n        sum++;<\/code><\/pre>\n\n\n\n
\u8fd9\u662f\u4e00\u4e2a\u5d4c\u5957for\u5faa\u73af\uff0c\u89c2\u5bdf\u5230\u5185\u5c42\u5bfb\u8ddf\u5916\u5c42\u5faa\u73af\u6709\u5173\u7cfb\uff0c\u6545\u6211\u4eec\u9700\u8981\u5217\u8868\u89e3\u51b3\uff082022\u5e74\u771f\u9898\uff09<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
18.\u6c42\u4e0b\u5217\u4ee3\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
int count = 0, i, j;\nfor (i = 1; i * i <= n; i++)\n    for (j = 1; j <= i; j++)\n        count++;<\/code><\/pre>\n\n\n\n
\u8fd9\u9898\u4e5f\u662f\u5d4c\u5957for\u5faa\u73af\uff0c\u76f4\u63a5\u7528\u8868\u683c\u6cd5\u5373\u53ef\u89e3\u51b3<\/p>\n\n\n\n
\u8fd9\u91cc\u9700\u8981\u8865\u5145\u4e00\u4e2a\u5e73\u65b9\u548c\u516c\u5f0f\uff1a\u2211<\/mo>i<\/mi>=<\/mo>1<\/mn><\/mrow>n<\/mi><\/msubsup>i<\/mi>2<\/mn><\/msup>=<\/mo>n<\/mi>(<\/mo>n<\/mi>+<\/mo>1<\/mn>)<\/mo>(<\/mo>2<\/mn>n<\/mi>+<\/mo>1<\/mn>)<\/mo><\/mrow>6<\/mn><\/mfrac><\/mrow>\\sum_{i=1}^n i^2 = \\frac{n(n+1)(2n+1)}{6}<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u516d \u603b\u7ed3<\/h2>\n\n\n\n
\u8fd9\u91cc\u9762\u603b\u7ed3\u4e86\u7edd\u5927\u591a\u6570\u65f6\u95f4\u590d\u6742\u5ea6\u95ee\u9898\u95ee\u9898\u4e00\u4e2a\u89e3\u6cd5\uff0c\u5bf9\u4e8e\u9012\u5f52\u6c42\u89e3\u7bc7\u5e45\u8f83\u5c0f\uff0c\u6709\u65f6\u95f4\u7684\u8bdd\u4f1a\u8865\u5145\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00 \u6982\u5ff5 \u65f6\u95f4\u590d\u6742\u5ea6\u63cf\u8ff0\u7b97\u6cd5\u6267\u884c\u65f6\u95f4\u968f\u95ee\u9898\u89c4\u6a21n\u589e\u5927\u800c\u53d8\u5316\u7684\u8d8b\u52bf,\u662f\u5173\u4e8en\u7684\u6e10\u8fd1\u51fd\u6570\u3002\u7b97\u6cd5\u6267\u884c\u65f6\u95f4\u901a\u5e38\u7531\u8bed\u53e5\u9891 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[25],"class_list":["post-82","post","type-post","status-publish","format-standard","hentry","category-sjjgysf","tag-sjjgysf"],"_links":{"self":[{"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/posts\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=82"}],"version-history":[{"count":2,"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/posts\/82\/revisions"}],"predecessor-version":[{"id":100,"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/posts\/82\/revisions\/100"}],"wp:attachment":[{"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=82"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=82"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.chenwenhao.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}