H****s 发帖数: 247 | 1 用经典DP肯定是O(N^3), 但是用经典递归呢(没有剪枝和caching)?
能想到的是:O(N) = O(N-1) + O(N-2) + O(N-3) + ... + O(1) + N
但怎么解啊? | H****s 发帖数: 247 | 2 居然没人回答,估计是我的问题太弱了,自己顶,把题目也贴在这里
Given a string s1, we may represent it as a binary tree by partitioning it
to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two
children.
For example, if we choose the node "gr" and swap its two children, it
produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
【在 H****s 的大作中提到】 : 用经典DP肯定是O(N^3), 但是用经典递归呢(没有剪枝和caching)? : 能想到的是:O(N) = O(N-1) + O(N-2) + O(N-3) + ... + O(1) + N : 但怎么解啊?
| j*****y 发帖数: 1071 | 3 recursive的 时间代价感觉是
T(n) = 2(T(1) + T(n - 1) + T(2) + T(n - 2) + ... + T(n - 1) + T(1)) =
4(T(1) + T(2) + ... + T(n - 1))
T(n) = O(5^n)
it
【在 H****s 的大作中提到】 : 居然没人回答,估计是我的问题太弱了,自己顶,把题目也贴在这里 : Given a string s1, we may represent it as a binary tree by partitioning it : to two non-empty substrings recursively. : Below is one possible representation of s1 = "great": : great : / \ : gr eat : / \ / \ : g r e at : / \
| H****s 发帖数: 247 | 4 感觉比较靠谱,等我有时间好好算算。
【在 j*****y 的大作中提到】 : recursive的 时间代价感觉是 : T(n) = 2(T(1) + T(n - 1) + T(2) + T(n - 2) + ... + T(n - 1) + T(1)) = : 4(T(1) + T(2) + ... + T(n - 1)) : T(n) = O(5^n) : : it
|
|