问答

当前位置

Flip Game II 搜索解法时间

  • Ta: D助教

老师好,

https://leetcode.com/problems/flip-game-ii/discuss/
请问这题搜索的时间和加记忆化搜索时间分别是多少?
单纯搜索的话, 我看lc discuss里说是(n -1) * (n - 3) * (n - 5) * .. = n!!
记忆化搜索的话, https://www.jiuzhang.com/qa/941/ 这里有讨论, 但我不是很理解为什么老师说是n^2

谢谢!

3 个回复

2017-11-10 华助教

应该是助教算错了。

给定长度为n的初始字符串,不同的字符串在DFS中能够达到的状态数不同,其中n个字符均为+所能达到的状态最多。

设f[n]表示长度为n且均为+所能达到的状态数,那么显然有f[1] = 1(+),f[2] = 2(++,--),f[3] = 3(+++,-++,+--),f[4] = 5(++++,--++,-++-,--++,----),f[n] = f[n - 1] + f[n - 2](考虑第一个字符为+,前两个字符为--)。

可见f[]为斐波那契数列,因此只考虑记忆化搜索中的状态数,就可以达到指数时间。

实际上,对于这一类记忆化搜索问题计算复杂度,一般计算复杂度的上界(采用大O符号)。我们采取的计算公式为,复杂度 = 状态数 * 决策数目 * 转移费用。

对于这道题而言,状态数上界为O(2^n),决策数目上界为O(n),转移费用为O(1),因此复杂度上界为O(n*2^n)。

这道题更优秀的做法是,通过计算SG函数(Sprague-Grundy Function)从而在O(n^2)复杂度内得到答案,具体可以参照题解。


2017-11-10 B同学

谢谢老师这么细心的讲解! 请问"复杂度 = 状态数 * 决策数目 * 转移费用" 中 决策数目和转移费用分别是什么意思, 套在这题是怎么算的?

以及这题搜索和记忆化搜索时间都是O(n2^n)?

我之前上九章课, dfs时间说的是O(状态数*计算每个状态所需时间), 不过本质应该跟你意思一样~


2017-11-11 华助教
  1. 因为在DFS的过程中,我需要枚举在哪些位置把++变成--,这个就是决策数目,它复杂度是O(n)的,同时,我们需要得到转移之后的状态的答案,如果我们用一个整数来表示每一个状态(第i位为+则整数的第i为为1否则为0)通过数组存储,那么我得到这个状态的时间就是O(1)的,如果采用二叉搜索树存储,那么我得到这个状态的时间就是O(log(n))的,这个就是转移费用。
  2. 暴力搜索的复杂度为O(n!!),记忆化搜索的复杂度为O(n*2^n)。
  3. 意思是一样的,计算每个状态所需时间实际上就是决策数目 * 转移费用。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1