{"id":4011,"date":"2018-09-17T19:16:30","date_gmt":"2018-09-18T02:16:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4011"},"modified":"2021-01-03T23:17:22","modified_gmt":"2021-01-04T07:17:22","slug":"amortized-analysis","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sp\/amortized-analysis\/","title":{"rendered":"\u82b1\u82b1\u9171 Amortized Analysis \u5747\u644a\u5206\u6790 SP7"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode Amortized Analysis \u5747\u644a\u5206\u6790 - \u5237\u9898\u627e\u5de5\u4f5c SP7\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/OwMhWDOxX94?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Amortized Analysis<\/strong><\/h1>\n<p>Amortized analysis can help us understand the actual cost of n operations on a data structure. Since some operations can be really fast e.g. O(1), but some operations can be really slow e.g. O(n). We could say the time complexity of that operation is O(n). However, it does not reflect the actual performance. And turns out, we can prove that certain operations have an amortized cost of O(1) while they can take O(n) in the worst case.<\/p>\n<p>\u5747\u644a\u5206\u6790\u53ef\u4ee5\u5e2e\u52a9\u6211\u4eec\u4e86\u89e3\u5bf9\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\u8fdb\u884cn\u6b21\u64cd\u4f5c\u7684\u771f\u5b9e\u4ee3\u4ef7\u3002\u5bf9\u4e8e\u76f8\u540c\u7684\u64cd\u4f5c\uff0c\u6709\u65f6\u5019\u53ef\u4ee5\u975e\u5e38\u5feb\uff0c\u4f8b\u5982\u5728O(1)\u65f6\u95f4\u5185\u5b8c\u6210\uff0c\u800c\u6709\u65f6\u5019\u5219\u9700\u8981O(n)\u3002\u6211\u4eec\u5f53\u7136\u53ef\u4ee5\u8bf4\u8fd9\u4e2a\u64cd\u4f5c\u6700\u574f\u60c5\u51b5\u4e0b\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff0c\u4f46\u662f\u8fd9\u5e76\u4e0d\u80fd\u771f\u5b9e\u53cd\u6620\u5b83\u7684\u5b9e\u9645\u590d\u6742\u5ea6\u3002\u901a\u8fc7\u5747\u644a\u5206\u6790\uff0c\u6211\u4eec\u53ef\u4ee5\u8bc1\u660e\uff0c\u5c3d\u7ba1\u6709\u4e9b\u64cd\u4f5c\u5728\u6700\u574f\u60c5\u51b5\u4e0b\u662fO(n)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u4f46\u662f\u5747\u644a\u4e0b\u6765\u53ea\u9700\u8981O(1)\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-large wp-image-4016\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p>&nbsp;<\/p>\n<h1>Dynamic Array<\/h1>\n<p>dynamic array doubles its size when it&#8217;s full which could take O(i) time where i is the number of elements in the array. Otherwise just store the element which only cost O(1). We can use aggregate method to compute the amortized cost of dynamic array.<\/p>\n<p>\u52a8\u6001\u6570\u7ec4\u5728\u5bb9\u91cf\u6ee1\u65f6\u5c06\u5bb9\u91cf\u7ffb\u7ffb\uff0c\u8fd9\u4e00\u6b65\u9700\u8981O(i)\u65f6\u95f4\uff0ci\u662f\u5f53\u524d\u6570\u7ec4\u4e2d\u7684\u5143\u7d20\u4e2a\u6570\u3002\u5982\u679c\u6ca1\u6709\u6ee1\uff0c\u53ea\u9700\u8981\u5c06\u5143\u7d20\u5b58\u50a8\u4e0b\u6765\u5373\u53ef\uff0c\u53ea\u9700\u8981\u82b1\u8d39O(1)\u65f6\u95f4\u3002\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u805a\u5408\u6cd5\u6765\u8ba1\u7b97\u5747\u644a\u6210\u672c\u3002<\/p>\n<p>((1 + 1) + (1 + 2) + (1) + (1 + 4) + (1) + (1) + (1) + (1+8) + &#8230; + (1+n)) \/ n, assuming n is 2^k.<\/p>\n<p>= (1 * n + (1 + 2 + 4 + 8 + &#8230; + n)) \/ n = (n + 2n &#8211; 1) \/ n = 3. O(1)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\nusing namespace std;\n\nclass DynamicArray {\npublic:\n  DynamicArray() {\n    data_ = new int[1];\n    capcity_ = 1;\n  }\n  void add(int x) {\n    data_[size_++] = x;\n    ++total_cost_;\n    if (size_ == capcity_) {\n      capcity_ *= 2;\n      total_cost_ += size_;\n      int* new_data = new int[capcity_];\n      copy(data_, data_ + size_, new_data);\n      swap(new_data, data_);\n      delete [] new_data;\n    }\n  }\n  int totalCost() const { return total_cost_; }\nprivate:\n  int total_cost_ = 0;\n  int size_ = 0;\n  int capcity_;\n  int* data_;\n};\n\nint main() {\n  DynamicArray arr;\n  for (int i = 1; i &lt;= 16; ++i) {\n    arr.add(i);\n    cout &lt;&lt; i &lt;&lt; \" average cost: \" &lt;&lt; arr.totalCost() \/ static_cast&lt;float&gt;(i) &lt;&lt; endl;\n  }\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Output<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:sh decode:true \">1 average cost: 2\n2 average cost: 2.5\n3 average cost: 2\n4 average cost: 2.75\n5 average cost: 2.4\n6 average cost: 2.16667\n7 average cost: 2\n8 average cost: 2.875\n9 average cost: 2.66667\n10 average cost: 2.5\n11 average cost: 2.36364\n12 average cost: 2.25\n13 average cost: 2.15385\n14 average cost: 2.07143\n15 average cost: 2\n16 average cost: 2.9375\n[Finished in 0.4s]<\/pre>\n<\/div><\/div>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4022 size-full\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Monotonic Stack<\/strong><\/h1>\n<p>\u4f8b\u5b502: \u5355\u8c03\u6808<\/p>\n<p>\u5f80\u5355\u8c03\u6808push\u4e00\u4e2a\u5143\u7d20\u7684\u65f6\u5019\uff0c\u4f1a\u5220\u9664\u4e0a\u6240\u6709\u5c0f\u4e8e\u7b49\u4e8e\u5b83\u7684\u5143\u7d20\u3002\u8fd9\u6b65\u64cd\u4f5c\u5728\u6700\u4f18\u60c5\u51b5\u4e0b\u662fO(1)\u65f6\u95f4\uff0c\u5982\u679c\u5b83\u6bd4\u6808\u9876\u5143\u7d20\u8981\u5c0f\u3002\u5728\u6700\u574f\u60c5\u51b5\u4e0b\u662fO(i)\u65f6\u95f4\uff0c\u6808\u4e0a\u6709i\u4e2a\u5143\u7d20\uff0c\u5b83\u6bd4\u8fd9i\u4e2a\u5143\u7d20\u90fd\u8981\u5927\uff0c\u6240\u4ee5\u4e00\u5171\u8981pop i\u6b21\u3002<\/p>\n<p>\u805a\u5408\u6cd5\uff1a<\/p>\n<p>\u7531\u4e8e\u6bcf\u4e2a\u5143\u7d20\u90fd\u4f1a\u88abpush\u5230\u6808\u4e0a\u53bb1\u6b21\uff0c\u6700\u591a\u4f1a\u88abpop1\u6b21\uff0c\u6240\u4ee5\u603b\u7684\u64cd\u4f5c\u6570 &lt;= 2n\u3002 2n \/ n = 2 O(1)\u3002<\/p>\n<p>\u4f1a\u8ba1\u6cd5\uff1a<\/p>\n<p>\u6bcf\u6b21push\u4e4b\u524d\u5148\u5b58k\u5757\u94b1\uff0ck=2, \u4e00\u5757\u94b1\u7528\u4e8epush\u81ea\u5df1\uff0c\u4e00\u5757\u94b1\u7559\u7740\u7528\u4e8epop\u81ea\u5df1\u3002<\/p>\n<p>push\u7684\u65f6\u5019\u6263\u96641\u5757\u94b1\uff0cpop\u7684\u65f6\u5019\u518d\u6263\u96641\u5757\u94b1\u3002\u4f46\u4e0d\u7ba1\u600e\u6837\uff0c\u6211\u7684\u8d26\u6237\u4e0a\u7684\u94b1\u6c38\u8fdc&gt;=0\u3002\u8fd9\u6837\u6211\u4eec\u53ef\u4ee5\u8bf4push\u7684\u5747\u644a\u6210\u672c\u662fk=2\u3002\u540c\u6837\u662fO(1)\uff0c\u5c3d\u7ba1\u5b83\u7684worst case\u662fO(n)\u3002<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\n#include &lt;stack&gt;\nusing namespace std;\n\nclass MonotonicStack {\npublic:\n  void push(int x) {\n    while (!data_.empty() &amp;&amp; x &gt; data_.top()) {\n      this-&gt;pop();\n    }\n    ++total_cost_;\n    data_.push(x);\n  }\n\n  int pop() {\n    ++total_cost_;\n    int t = data_.top();\n    data_.pop();\n    return t;\n  }\n  int totalCost() const { return total_cost_; }\nprivate:\n  int total_cost_ = 0;\n  stack&lt;int&gt; data_;\n};\n\nint main() {\n  srand(1);\n  MonotonicStack s;\n  for (int i = 1; i &lt;= 32; ++i) {\n    s.push(rand());\n    cout &lt;&lt; i &lt;&lt; \" average cost: \" &lt;&lt; s.totalCost() \/ static_cast&lt;float&gt;(i) &lt;&lt; endl;\n  }  \n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Output<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:sh decode:true \">1 average cost: 1\n2 average cost: 1.5\n3 average cost: 1.66667\n4 average cost: 1.5\n5 average cost: 1.6\n6 average cost: 1.5\n7 average cost: 1.42857\n8 average cost: 1.75\n9 average cost: 1.77778\n10 average cost: 1.9\n11 average cost: 1.81818\n12 average cost: 1.83333\n13 average cost: 1.84615\n14 average cost: 1.78571\n15 average cost: 1.8\n16 average cost: 1.8125\n17 average cost: 1.82353\n18 average cost: 1.77778\n19 average cost: 1.78947\n20 average cost: 1.75\n21 average cost: 1.80952\n22 average cost: 1.86364\n23 average cost: 1.82609\n24 average cost: 1.91667\n25 average cost: 1.88\n26 average cost: 1.84615\n27 average cost: 1.81481\n28 average cost: 1.85714\n29 average cost: 1.82759\n30 average cost: 1.86667\n31 average cost: 1.90323\n32 average cost: 1.875\n[Finished in 0.5s]<\/pre>\n<\/div><\/div>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4014\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/sp7-3.png\" alt=\"\" width=\"960\" height=\"540\"><\/p>\n<h1><strong>Related Problem<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-901-online-stock-span\/\">\u82b1\u82b1\u9171 LeetCode 901. Online Stock Span<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Amortized Analysis Amortized analysis can help us understand the actual cost of n operations on a data structure. Since some operations can be really fast&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[170],"tags":[],"class_list":["post-4011","post","type-post","status-publish","format-standard","hentry","category-sp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4011","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4011"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4011\/revisions"}],"predecessor-version":[{"id":7909,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4011\/revisions\/7909"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}