Palindrome Partitioning算法的时间复杂度是多少？ [英] What's the time complexity of this algorithm for Palindrome Partitioning?

问题描述

Palindrome分区

给定一个字符串s，
分区是回文。
返回所有可能的回文
分区。

我个人认为，时间复杂度是O（n ^ n），n是给定字符串的长度。

谢谢< > Dan Roche ，紧缩时间复杂度= O（n *（2 ^ n）），请检查下面的详细信息。

  #include< vector> 
 using namespace std; 
 
类解决方案{
 public：
 vector< vector< string> partition（string s）{
 vector< vector< string>>列表; 
 vector< string> subList; 
 
 //输入验证。 
 if（s.length（）< = 1）{
 subList.push_back（s）; 
 list.push_back（subList）; 
 return list; 
} 
 
 int len = s.length（）; 
 vector< vector< bool>> memo（len，vector< bool>（len））; 
 for（int i = 0; i  for（int j = 0; j  if ; = j）memo [i] [j] = true; 
 else memo [i] [j] = false; 
} 
} 
 
 int begin = 0; 
 helper（s，start，list，subList，memo）; 
 
返回列表; 
} 
 
 void helper（string s，int start，
 vector< vector< string>& list，vector< string>& subList，
 vector< vector< bool>& memo）{
 
 //基本情况。 
 if（start> s.length（） -  1）{
 vector< string> one_rest（subList）; 
 list.push_back（one_rest）; 
 return; 
} 
 
 for（int len = 1; start + len <= s.length（）; len ++）{
 int end = start + len  - 
 
 memo [start] [end] =（len == 1）|| 
（memo [start + 1] [end  -  1]&& s [start] == s [end]）; 
 
 if（memo [start] [end] == true）{
 //尝试。 
 subList.push_back（s.substr（start，len））; 
 
 //执行递归。 
 helper（s，end + 1，list，subList，memo）; 
 
 //回滚。 
 subList.pop_back（）; 
} 
} 
} 
}; 
  

解决方案

最糟糕的运行时间是O 2 ^ n）。这当然是指数，你怀疑，但不如O（n ^ n）。

这是我得到O（n * 2 ^ n）：顶层函数有一个O（n ^ 2）循环来初始化memo，然后调用helper对整个字符串。因此，如果我们使用（s.length（） - start）等于n来编写H（n）来调用helper，那么算法的总成本

cost = H（n）+ O（n ^ 2）

H（n）的基本情况是 s.length（） - start 等于1，然后它只是复制列表：

H（1）= O（n）

b $ b

对于递归的情况，如果 if condition memo [start] [end] （n-1），（n-2），（n-3），...（n-1）次递归调用。 ，2，1.除了对 helper 的递归调用，还必须调用 substr 相同的尺寸，其总共花费O（n ^ 2）。因此，总的来说，对于n> 1的H（n）的成本是

H（n）= H（n-1）+ H（n-2）+ ... + H（1）+ O（n ^ 2）

）

现在你可以为H（n-1）写相同的表达式，然后代入回简化： / p>

H（n）= 2 H（n-1）+ O（n）

这解决了

H（n）= O（n * 2 ^ n）

由于它大于O（n ^ 2），整个成本也是O（n * 2 ^ n）。

---

注意：您可以通过预先计算前面的所有子字符串单个O（n ^ 3）循环。您也可以对 memo 数组执行相同的操作。然而，这不改变渐近的大O绑定。

事实上，O（n * 2 ^ n）是最佳的，因为在最坏的情况下，字符串是相同字符的n次重复，如aaaaaa，在这种情况下，对于总输出大小，存在2 ^ n个可能的分区，每个具有大小n。（n * 2 ^ n） >

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.

Personally I think, the time complexity is O(n^n), n is the length of the given string.

Thank you Dan Roche, the tight time complexity = O(n* (2^n)), check details below.

#include <vector>
using namespace std;

class Solution {
public:
vector<vector<string>> partition(string s) {
    vector<vector<string>> list;
    vector<string> subList;

    // Input validation.
    if (s.length() <= 1) {
        subList.push_back(s);
        list.push_back(subList);
        return list;
    }

    int len = s.length();
    vector<vector<bool>> memo(len, vector<bool>(len));
    for (int i = 0; i < len; i ++) {
        for (int j = 0; j < len; j ++) {
            if (i >= j) memo[i][j] = true;
            else memo[i][j] = false;
        }
    }

    int start = 0;
    helper(s, start, list, subList, memo);

    return list;
}

void helper(string s, int start, 
            vector<vector<string>> &list, vector<string> &subList,
            vector<vector<bool>> &memo) {

    // Base case.
    if (start > s.length() - 1) {
        vector<string> one_rest(subList);
        list.push_back(one_rest);
        return;
    }

    for (int len = 1; start + len <= s.length(); len ++) {
        int end = start + len - 1;

        memo[start][end] = (len == 1) ||
                           (memo[start + 1][end - 1] && s[start] == s[end]);

        if (memo[start][end] == true) {
            // Have a try.
            subList.push_back(s.substr(start, len));

            // Do recursion.
            helper(s, end + 1, list, subList, memo);

            // Roll back.
            subList.pop_back();
        }
    }
}
};

解决方案

The worst-case running time is O(n * 2^n). This is of course exponential as you suspected, but not as bad as O(n^n).

Here's how I got O(n * 2^n): Your top-level function has an O(n^2) loop to initialize memo, and then a call to helper on the entire string. So if we write H(n) for the cost of calling helper with (s.length()-start) equal to n, then the total cost of your algorithm will be

cost = H(n) + O(n^2)

The base case for H(n) is when s.length() - start equals 1, and then it's just the cost of copying the list:

H(1) = O(n)

And for the recursive case, if the if condition memo[start][end] is true every time, there will be (n-1) recursive calls on size (n-1), (n-2), (n-3), ..., 2, 1. In addition to these recursive calls to helper, you also have to call the substr function on the same sizes, which costs O(n^2) in total. So overall the cost of H(n), for n>1, is

H(n) = H(n-1) + H(n-2) + ... + H(1) + O(n^2)

(I would write that as a summation but SO doesn't have LaTeX support.)

Now you can write the same expression for H(n-1), then substitute back to simplify:

H(n) = 2 H(n-1) + O(n)

And this solves to

H(n) = O(n * 2^n)

Since that is larger than O(n^2), the whole cost is also O(n * 2^n).

---

Note: You could slightly improve this by pre-computing all the substrings up front, in a single O(n^3) loop. You might as well do the same for the memo array. However, this doesn't change the asymptotic big-O bound.

In fact, O(n * 2^n) is optimal, because in the worst case the string is a repetition of the same character n times, like "aaaaaa", in which case there are 2^n possible partitions, each having size n, for a total output size of Ω(n * 2^n).

这篇关于Palindrome Partitioning算法的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！