Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
51 lines (30 sloc) 2.03 KB

找零钱的代码可以在这里找到。 首先是画出11美分的计算过程:

我这里偷了个懒,在网上找了个图片,不过我自己还是在本子上画了一边的,绝对不会偷工减料。

然后是时间、空间复杂度的分析:

###空间复杂度

由于count-change过程也是个树形递归,而且在计算某一节点时,只需要保存起上面分支的节点即可,所以这里的复杂度是O(n)

更准确些:假设硬币最小面额为a,硬币种类数为m,零钱数为n,那么树形递归的最长分支应该是floor(n/a)+m

###时间复杂度

由于count-change过程是个树形递归,而且只有两个分支,也就是二叉树,时间复杂度应该就相当于二叉树中的节点数,全二叉树的复杂度是2n,所以我认为这里的时间复杂度也是2n

但是在网上找到一篇文章(需翻墙),证明了时间复杂度为O(nm),在本题中m=5。但是这篇文章是用数学归纳法证明的,有些不好理解,我这里给我网上的另一种简单的分析法,这两者结合起来就好理解些了:

假设T(n,m)(cc n m)所需要度计算步数。

那么当m=1时,计算过程如下:

从上图可以看出:

T(n, 1) = 2n + 1

也就是O(n)

m=2时,计算过程如下:

从最右侧分支可以看到,一共调用了n/5(cc n 2),而且每次调用(cc n 2)时都会产生一个完整的(cc n 1)的过程。这也就是说:

T(n, 2) = (n/5)*(2n+1)

也就是O(n2)。

类似的,当我们在算m=3时,有如下图的计算过程:

可以得到时间复杂度为O(n3)。

这样一直类比下来,我们就能够类比出m=5时,时间复杂度为O(n5)。