{"id":1777,"date":"2018-02-07T20:48:37","date_gmt":"2018-02-08T04:48:37","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1777"},"modified":"2018-02-08T08:21:41","modified_gmt":"2018-02-08T16:21:41","slug":"time-space-complexity-of-recursion-functions-sp4","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sp\/time-space-complexity-of-recursion-functions-sp4\/","title":{"rendered":"\u82b1\u82b1\u9171  Time\/Space Complexity of Recursion Functions SP4"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 Time\/Space Complexity of Recursive Algorithms  - \u5237\u9898\u627e\u5de5\u4f5c SP4\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/OQi4n8EKRD8?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<p>&nbsp;<\/p>\n<p>How to analyze the time and space complexity of a recursion function?<\/p>\n<p>\u5982\u4f55\u5206\u6790\u4e00\u4e2a\u9012\u5f52\u51fd\u6570\u7684\u65f6\u95f4\/\u7a7a\u95f4\u590d\u6742\u5ea6\uff1f<\/p>\n<p>We can answer that using <a href=\"https:\/\/en.wikipedia.org\/wiki\/Master_theorem_(analysis_of_algorithms)\">master theorem<\/a> or induction in most of the cases.<\/p>\n<p>\u5728\u5927\u90e8\u5206\u65f6\u5019\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u4e3b\u65b9\u6cd5\u548c\u6570\u5b66\u5f52\u7eb3\u6cd5\u6765\u8fdb\u884c\u89e3\u7b54\u3002<\/p>\n<p>First of all, we need to write down the recursion relation of a function.<\/p>\n<p>\u9996\u5148\u6211\u4eec\u8981\u5199\u51fa\u4e00\u4e2a\u51fd\u6570\u7684\u9012\u5f52\u8868\u8fbe\u5f0f\u3002<\/p>\n<pre class=\"lang:default decode:true\">def func(n):\r\n  if n &lt; 0: return 1\r\n  return func(n\/2) + func(n\/2)<\/pre>\n<p>Let&#8217;s use T(n) to denote the running time of func with input size of n.<\/p>\n<p>\u8ba9\u6211\u4eec\u7528T(n)\u6765\u8868\u793afunc\u51fd\u6570\u5728\u8f93\u5165\u89c4\u6a21\u4e3an\u7684\u8fd0\u884c\u65f6\u95f4\u3002<\/p>\n<p>Then we have\uff1a<\/p>\n<p>\u90a3\u4e48\u6211\u4eec\u6709\uff1a<\/p>\n<p>T(n) = 2*T(n\/2) + O(1)<\/p>\n<p>a = 2, b = 2, c_crit = logb(a) = 1, f(n) = n^c, c = 0.<\/p>\n<p>c &lt; c_crit,\u00a0apply master theorem case 1:<\/p>\n<p>\u6839\u636e\u4e3b\u65b9\u6cd5\u7b2c\u4e00\u6761\u6211\u4eec\u5f97\u5230<\/p>\n<p>T(n) =\u00a0 \u0398(n^c_crit) = \u0398(n)<\/p>\n<p>&nbsp;<\/p>\n<p>Let&#8217;s look at another example:<\/p>\n<pre class=\"lang:python decode:true\">def func(n):\r\n  if n &lt; 0: return 1\r\n  s = 0\r\n  for i in range(n):\r\n    s += i\r\n  return s + func(n\/2) + func(n\/2)<\/pre>\n<p>T(n) = 2*T(n\/2) + O(n)<\/p>\n<p>a = 2, b = 2, c_crit = logb(a) = 1, f(n) = n^c, c = 1,<\/p>\n<p>c = c_crit,\u00a0apply master theorem case 2:<\/p>\n<p>\u6839\u636e\u4e3b\u65b9\u6cd5\u7b2c\u4e8c\u6761\u6211\u4eec\u5f97\u5230<\/p>\n<p>T(n) =\u0398(n^c_crit * (logn)^1)) = \u0398(nlogn)<\/p>\n<p><strong>Cheatsheet<\/strong><\/p>\n<table>\n<tbody>\n<tr>\n<th>Equation<\/th>\n<th>Time<\/th>\n<th>Space<\/th>\n<th>Examples<\/th>\n<\/tr>\n<tr>\n<td>T(n) = 2*T(n\/2) + O(n)<\/td>\n<td>O(nlogn)<\/td>\n<td>O(logn)<\/td>\n<td>quick_sort<\/td>\n<\/tr>\n<tr>\n<td>T(n) = 2*T(n\/2) + O(n)<\/td>\n<td>O(nlogn)<\/td>\n<td>O(n + logn)<\/td>\n<td>merge_sort<\/td>\n<\/tr>\n<tr>\n<td>T(n) = T(n\/2) + O(1)<\/td>\n<td>O(logn)<\/td>\n<td>O(logn)<\/td>\n<td>Binary search<\/td>\n<\/tr>\n<tr>\n<td>T(n) = 2*T(n\/2) + O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(logn)<\/td>\n<td>Binary tree traversal<\/td>\n<\/tr>\n<tr>\n<td>T(n) = T(n-1) + O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>Binary tree traversal<\/td>\n<\/tr>\n<tr>\n<td>T(n) = T(n-1) + O(n)<\/td>\n<td>O(n^2)<\/td>\n<td>O(n)<\/td>\n<td>quick_sort(worst case)<\/td>\n<\/tr>\n<tr>\n<td>T(n) = n * T(n-1)<\/td>\n<td>O(n!)<\/td>\n<td>O(n)<\/td>\n<td>permutation<\/td>\n<\/tr>\n<tr>\n<td>T(n) = T(n-1)+T(n-2)+&#8230;+T(1)<\/td>\n<td>O(2^n)<\/td>\n<td>O(n)<\/td>\n<td>combination<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p><strong>For recursion with memorization:<\/strong><\/p>\n<p>Time complexity: |# of subproblems| * |exclusive running time of a subproblem|<\/p>\n<p>Space complexity:|# of subproblems|\u00a0 + |max recursion depth| *\u00a0|space complexity of a subproblem|<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"lang:python decode:true\">def fib(n):\r\n  if n &lt; 1: return 1\r\n  if m[n]: return m[n]\r\n  m[n] = fib(n - 1) + fib(n - 2)\r\n  return m[n]<\/pre>\n<p>To solve fib(n), there are n subproblems fib(0), fib(1), &#8230;, fib(n)<\/p>\n<p>each sub problem takes O(1) to solve<\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n) + O(n) * O(1) = O(n)<\/p>\n<p><strong>Example 2:<\/strong><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-741-cherry-pickup\/\">LC 741 Cherry Pickup<\/a><\/p>\n<pre class=\"lang:python decode:true\">dp(x1, y1, x2):\r\n if min(x1, y1, x2) &lt; 0: return 0\r\n if m[x1][y1][x2]: return m[x1][y1][x2]\r\n ans = max(dp(x1 - 1, y1, x2 - 1), \r\n           dp(x1, y1 - 1, x2),\r\n           dp(x1, y1 - 1, x2 - 1), \r\n           dp(x1 - 1, y1, x2))\r\n m[x1][y1][x2] = ans\r\n return m[x1][y1][x2]\r\n<\/pre>\n<p>To solve dp(n, n, n), there are n^3 subproblems<\/p>\n<p>each subproblem takes O(1) to solve<\/p>\n<p>Max recursion depth O(n)<\/p>\n<p>Time complexity: O(n^3) * O(1) = O(n^3)<\/p>\n<p>Space complexity: O(n^3) + O(n) * O(1) = O(n^3)<\/p>\n<p><strong>Example 3:<\/strong><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-312-burst-balloons\/\">LC 312: Burst Balloon<\/a><\/p>\n<pre class=\"lang:python decode:true\">dp(i, j):\r\n if m[i][j]: return m[i][j]\r\n for k in range(i, j + 1):\r\n   ans = max(ans, dp(i, k - 1) + C + dp(k + 1, j))\r\n m[i][j] = ans\r\n return m[i][j]\r\n<\/pre>\n<p>To solve dp(0, n), there are n^2 subproblems dp(0, 0), dp(0, 1), &#8230;, dp(n-1, n)<\/p>\n<p>each subproblem takes O(n) to solve<\/p>\n<p>Max recursion depth O(n)<\/p>\n<p>Time complexity: O(n^2) * O(n) = O(n^3)<\/p>\n<p>Space complexity: O(n^2) + O(n) * O(1) = O(n^2)<\/p>\n<p><strong>Slides:<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1783\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1781\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/> <img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1782\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1780\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-4.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1779\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-5.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-5.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-5-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-5-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1778\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-6.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-6.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-6-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/sp4-6-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; How to analyze the time and space complexity of a recursion function? \u5982\u4f55\u5206\u6790\u4e00\u4e2a\u9012\u5f52\u51fd\u6570\u7684\u65f6\u95f4\/\u7a7a\u95f4\u590d\u6742\u5ea6\uff1f We can answer that using master theorem or induction in most&#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":[161,220,219],"class_list":["post-1777","post","type-post","status-publish","format-standard","hentry","category-sp","tag-recusion","tag-space-complexity","tag-time-complexity","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1777","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=1777"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1777\/revisions"}],"predecessor-version":[{"id":1795,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1777\/revisions\/1795"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1777"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1777"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1777"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}