活跃农民
- 积分
- 472
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2009-8-24
- 最后登录
- 1970-1-1
|
回复 nooneknow
应该达不到O(n)吧,你上面的代码有一个问题,如果左右儿子分别相等,你就直接左边跟左边比,右边跟右边比,这是不完整的。如果左右相等的话,就需要(左左 右右) + (左右 右左)两种情况都试一遍才行。我觉得上面8楼的代码是对的,T(n) = 4T(n/2) + O(1) T(n) = O(n^2)。这题应该很难再降低复杂度了。
darksteel 发表于 2011-11-1 08:51 ![]()
不考虑元素duplicates的话,每个node只用扫2遍。复杂度O(2n)。
或者这么想,无论是不是swap,最多只有一个可能性返回true。
需不需要swap,下一层递归马上就能知道。不需要递归下去。
递归式是T(n) = T(n - 1) + O(1)。
如果考虑duplicates,worst case是每个node的值都一样。相当于只比较树长得像不像。
这样每个node都要考虑swap或者不swap。复杂度是指数级。 |
|