{"id":2209,"date":"2021-08-27T22:22:40","date_gmt":"2021-08-27T14:22:40","guid":{"rendered":"https:\/\/jimmyswebnote.com\/?p=2209"},"modified":"2021-10-30T20:11:39","modified_gmt":"2021-10-30T12:11:39","slug":"algorithms-big-o-notation","status":"publish","type":"post","link":"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/","title":{"rendered":"\u6f14\u7b97\u6cd5\u7b46\u8a18 1 \u2013 \u6f14\u7b97\u6cd5\u5b9a\u7fa9\u8207 Big O Notation"},"content":{"rendered":"\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-6633524b1f9f0\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-6633524b1f9f0\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#1_%E6%BC%94%E7%AE%97%E6%B3%95%E5%AE%9A%E7%BE%A9\" title=\"1. \u6f14\u7b97\u6cd5\u5b9a\u7fa9\">1. \u6f14\u7b97\u6cd5\u5b9a\u7fa9<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#11_%E8%BC%B8%E5%85%A5%EF%BC%88Input%EF%BC%89\" title=\"1.1 \u8f38\u5165\uff08Input\uff09\">1.1 \u8f38\u5165\uff08Input\uff09<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#12_%E8%BC%B8%E5%87%BA%EF%BC%88Output%EF%BC%89\" title=\"1.2 \u8f38\u51fa\uff08Output\uff09\">1.2 \u8f38\u51fa\uff08Output\uff09<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#13_%E6%9C%89%E9%99%90%E6%80%A7%EF%BC%88Finiteness%EF%BC%89\" title=\"1.3 \u6709\u9650\u6027\uff08Finiteness\uff09\">1.3 \u6709\u9650\u6027\uff08Finiteness\uff09<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#14_%E6%98%8E%E7%A2%BA%E6%80%A7%EF%BC%88Definiteness%EF%BC%89\" title=\"1.4 \u660e\u78ba\u6027\uff08Definiteness\uff09\">1.4 \u660e\u78ba\u6027\uff08Definiteness\uff09<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#15_%E6%9C%89%E6%95%88%E6%80%A7%EF%BC%88Effectiveness%EF%BC%89\" title=\"1.5 \u6709\u6548\u6027\uff08Effectiveness\uff09\">1.5 \u6709\u6548\u6027\uff08Effectiveness\uff09<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#2_Big_O_Notation\" title=\"2. Big O Notation\">2. Big O Notation<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#21_%E5%8F%AA%E4%BF%9D%E7%95%99%E6%9C%80%E9%AB%98%E6%AC%A1%E9%A0%85\" title=\"2.1 \u53ea\u4fdd\u7559\u6700\u9ad8\u6b21\u9805\">2.1 \u53ea\u4fdd\u7559\u6700\u9ad8\u6b21\u9805<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#22_%E5%B8%B8%E6%95%B8%E9%A0%85%E9%99%8D%E7%82%BA_1\" title=\"2.2 \u5e38\u6578\u9805\u964d\u70ba 1\">2.2 \u5e38\u6578\u9805\u964d\u70ba 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#23_log_%E7%9C%81%E7%95%A5%E5%BA%95%E6%95%B8\" title=\"2.3 log \u7701\u7565\u5e95\u6578\">2.3 log \u7701\u7565\u5e95\u6578<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#24_%E5%B8%B8%E8%A6%8B%E7%9A%84_Big_O_%E6%AF%94%E8%BC%83%EF%BC%9A\" title=\"2.4 \u5e38\u898b\u7684 Big O \u6bd4\u8f03\uff1a\">2.4 \u5e38\u898b\u7684 Big O \u6bd4\u8f03\uff1a<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/#3_%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99\" title=\"3. \u53c3\u8003\u8cc7\u6599\">3. \u53c3\u8003\u8cc7\u6599<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"1_%E6%BC%94%E7%AE%97%E6%B3%95%E5%AE%9A%E7%BE%A9\"><\/span>1. \u6f14\u7b97\u6cd5\u5b9a\u7fa9<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u4e00\u822c\u4f86\u8aaa\uff0c\u7b26\u5408\u4ee5\u4e0b\u9019 5 \u7a2e\u7279\u6027\uff08Characteristics\uff09\u5c31\u53ef\u4ee5\u7a31\u70ba\u6f14\u7b97\u6cd5\uff1a<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"11_%E8%BC%B8%E5%85%A5%EF%BC%88Input%EF%BC%89\"><\/span>1.1 \u8f38\u5165\uff08Input\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>An algorithm may have many inputs or no inputs at all.<\/p>\n\n\n\n<p>\u6f14\u7b97\u6cd5\u61c9\u8a72\u5177\u6709 0 \u500b\u6216\u591a\u500b\u8f38\u5165\u3002<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"12_%E8%BC%B8%E5%87%BA%EF%BC%88Output%EF%BC%89\"><\/span>1.2 \u8f38\u51fa\uff08Output\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>An algorithm should result at least one output.<\/p>\n\n\n\n<p>\u6f14\u7b97\u6cd5\u81f3\u5c11\u8981\u6709\u4e00\u500b\u6216\u591a\u500b\u8f38\u51fa\uff0c\u4e0d\u5141\u8a31 0 \u500b\u8f38\u51fa\u3002<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"13_%E6%9C%89%E9%99%90%E6%80%A7%EF%BC%88Finiteness%EF%BC%89\"><\/span>1.3 \u6709\u9650\u6027\uff08Finiteness\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>An algorithm should have finite number of steps and it should end after a finite time.<\/p>\n\n\n\n<p>\u6f14\u7b97\u6cd5\u9700\u8981\u5728\u6709\u9650\u7684\u6b65\u9a5f\u53ca\u6709\u9650\u7684\u6642\u9593\u5167\u5b8c\u6210\uff0c\u4e0d\u80fd\u6709\u7121\u7aae\u8ff4\u5708\u3002<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"14_%E6%98%8E%E7%A2%BA%E6%80%A7%EF%BC%88Definiteness%EF%BC%89\"><\/span>1.4 \u660e\u78ba\u6027\uff08Definiteness\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>Each step must be clear, well-defined and precise. There should be no any ambiguity.<\/p>\n\n\n\n<p>\u6f14\u7b97\u6cd5\u7684\u6bcf\u500b\u6b65\u9a5f\u5730\u9808\u6e05\u695a\u5b9a\u7fa9\uff0c\u4e0d\u5141\u8a31\u6709\u6a21\u7cca\u7684\u7a7a\u9593\u3002<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"15_%E6%9C%89%E6%95%88%E6%80%A7%EF%BC%88Effectiveness%EF%BC%89\"><\/span>1.5 \u6709\u6548\u6027\uff08Effectiveness\uff09<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>The algorithm should be possible and practicable in real life. It should not be abstract or imaginary.<\/p>\n\n\n\n<p>\u6f14\u7b97\u6cd5\u7684\u6bcf\u500b\u6b65\u9a5f\u90fd\u5fc5\u9808\u662f\u6709\u6548\u7684\u4e14\u53ef\u5728\u6709\u9650\u7684\u6b21\u6578\u5167\u57f7\u884c\u5b8c\u6210\u3002<\/p>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"2_Big_O_Notation\"><\/span>2. Big O Notation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Big O notation \u662f\u7528\u4f86\u5206\u6790\u6f14\u7b97\u6cd5\u6548\u7387\u7684\u6578\u5b78\u7b26\u865f\u3002<\/p>\n\n\n\n<p>\u5728\u5206\u6790\u4e00\u500b f(n) \u7684\u6f14\u7b97\u6cd5\u6642\uff0c\u90fd\u662f\u4ee5 n \u8da8\u8fd1\u65bc\u6975\u9650\u4f86\u8003\u91cf\uff0c\u56e0\u6b64\u6703\u4ee5\u4ee5\u4e0b\u539f\u5247\u4f86\u8a08\u7b97 Big O\uff1a<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"21_%E5%8F%AA%E4%BF%9D%E7%95%99%E6%9C%80%E9%AB%98%E6%AC%A1%E9%A0%85\"><\/span>2.1 \u53ea\u4fdd\u7559\u6700\u9ad8\u6b21\u9805<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>f(n) = n<sup>3<\/sup> + 100n<sup>2<\/sup> + 50n + 9 \u7684 Big O \u662f n<sup>3<\/sup>\uff0c\u4e5f\u53ef\u4ee5\u5beb\u4f5c O(n<sup>3<\/sup>)<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"22_%E5%B8%B8%E6%95%B8%E9%A0%85%E9%99%8D%E7%82%BA_1\"><\/span>2.2 \u5e38\u6578\u9805\u964d\u70ba 1<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>f(n) = 20n<sup>3<\/sup> + 100n<sup>2<\/sup> + 50n + 9  =&gt; O(n<sup>3<\/sup>)<\/p>\n\n\n\n<p>f(n) = 50 =&gt; O(1)<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"23_log_%E7%9C%81%E7%95%A5%E5%BA%95%E6%95%B8\"><\/span>2.3 log \u7701\u7565\u5e95\u6578<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>f(n) = log<sub>2<\/sub>n =&gt; O(logn)<\/p>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"24_%E5%B8%B8%E8%A6%8B%E7%9A%84_Big_O_%E6%AF%94%E8%BC%83%EF%BC%9A\"><\/span>2.4 \u5e38\u898b\u7684 Big O \u6bd4\u8f03\uff1a<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p> O(1) &lt; O(log n) &lt; O(n) &lt; O(n log n) &lt; O(n<sup>2<\/sup>) &lt; O(2^n) &lt; O(n!)<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><a href=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2021\/10\/svgexport-1-1.svg\"><img loading=\"lazy\" src=\"https:\/\/jimmyswebnote.com\/wp-content\/uploads\/2021\/10\/svgexport-1-1.svg\" alt=\"\u6f14\u7b97\u6cd5\u5b9a\u7fa9\" class=\"wp-image-2250\" width=\"800\" height=\"500\"\/><\/a><figcaption><span class=\"has-inline-color has-black-color\">\u5716<\/span>\u7247<span class=\"has-inline-color has-black-color\">\u4f86\u6e90<\/span>\uff1a<a href=\"https:\/\/www.bigocheatsheet.com\/\" target=\"_blank\" rel=\"noreferrer noopener\">Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell<\/a><\/figcaption><\/figure><\/div>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"3_%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99\"><\/span>3. \u53c3\u8003\u8cc7\u6599<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><a href=\"https:\/\/www.codesansar.com\/computer-basics\/algorithms.htm\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/www.codesansar.com\/computer-basics\/algorithms.htm\" rel=\"noreferrer noopener\">Algorithms (Characteristics, Guidelines &amp; Advantages)<\/a><br><a href=\"https:\/\/www.analyticssteps.com\/blogs\/what-algorithm-types-applications-characteristics\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/www.analyticssteps.com\/blogs\/what-algorithm-types-applications-characteristics\" rel=\"noreferrer noopener\">What is an Algorithm? Types, Applications, and Characteristics<br><\/a><a href=\"https:\/\/zh.wikipedia.org\/wiki\/%E7%AE%97%E6%B3%95\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/zh.wikipedia.org\/wiki\/%E7%AE%97%E6%B3%95\" rel=\"noreferrer noopener\">\u6f14\u7b97\u6cd5- \u7dad\u57fa\u767e\u79d1\uff0c\u81ea\u7531\u7684\u767e\u79d1\u5168\u66f8<\/a><br><a href=\"http:\/\/view-source:https:\/\/en.wikipedia.org\/wiki\/Algorithm_characterizations\" target=\"_blank\" data-type=\"URL\" data-id=\"view-source:https:\/\/en.wikipedia.org\/wiki\/Algorithm_characterizations\" rel=\"noreferrer noopener\">Algorithm characterizations &#8211; Wikipedia<\/a><br><a href=\"https:\/\/www.bigocheatsheet.com\/\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/www.bigocheatsheet.com\/\" rel=\"noreferrer noopener\">Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell<\/a><\/p>\n\n\n\n\n\n<p>\u5982\u679c\u89ba\u5f97\u6211\u7684\u6587\u7ae0\u6709\u5e6b\u52a9\u7684\u8a71\uff0c\u6b61\u8fce\u5e6b\u6211\u7684\u7c89\u5c08\u6309\u8b9a\u54e6~\u8b1d\u8b1d\u4f60\uff01<br><\/p>\n\n<iframe loading=\"lazy\" src=\"https:\/\/www.facebook.com\/plugins\/page.php?href=https%3A%2F%2Fwww.facebook.com%2Fjimmyswebnote&amp;tabs=timeline&amp;width=340&amp;height=500&amp;small_header=false&amp;adapt_container_width=true&amp;hide_cover=false&amp;show_facepile=true&amp;appId\" width=\"340\" height=\"500\" style=\"border:none;overflow:hidden\" scrolling=\"no\" frameborder=\"0\" allowfullscreen=\"true\" allow=\"autoplay; clipboard-write; encrypted-media; picture-in-picture; web-share\"><\/iframe>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>1. \u6f14\u7b97\u6cd5\u5b9a\u7fa9 \u4e00\u822c\u4f86\u8aaa\uff0c\u7b26\u5408\u4ee5\u4e0b\u9019 5 \u7a2e\u7279\u6027\uff08Characteristics\uff09\u5c31\u53ef\u4ee5\u7a31\u70ba\u6f14\u7b97\u6cd5\uff1a 1.1 \u8f38\u5165\uff08Input\uff09 An algorithm may &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/jimmyswebnote.com\/algorithms-big-o-notation\/\"> <span class=\"screen-reader-text\">\u6f14\u7b97\u6cd5\u7b46\u8a18 1 \u2013 \u6f14\u7b97\u6cd5\u5b9a\u7fa9\u8207 Big O Notation<\/span> Read More \u00bb<\/a><\/p>\n","protected":false},"author":1,"featured_media":2216,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[148,147],"tags":[150,149],"_links":{"self":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2209"}],"collection":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/comments?post=2209"}],"version-history":[{"count":1,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2209\/revisions"}],"predecessor-version":[{"id":2251,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2209\/revisions\/2251"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/media\/2216"}],"wp:attachment":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/media?parent=2209"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/categories?post=2209"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/tags?post=2209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}