时间戳

首页 > 解决方案 > 函数的时间复杂度是多少？

c++ - 函数的时间复杂度是多少？

问题描述

今天我正在解决断词问题，但我无法计算实施解决方案的时间复杂度。

这是问题：- https://practice.geeksforgeeks.org/problems/word-break-part-2/0/

我们必须从测试用例中提供的字典中包含的单词中找到并打印由给定字符串组成的每个句子。

示例：- string = "snakesandladder", dictionary = ["snake", "snakes", "and", "sand", "ladder"]。

一个解决方案是[“蛇和梯”，“蛇沙梯”]。

我实现的功能：-

set<vector<string>> res; `//stores all the sentences`
vector<string> v; `//stores all the words in a sentence`
helper(s, st, 0); `//function call`

void helper(string& s, unordered_set<string>& st, int i){
`//string s is the string and unordered_set<string> st is the dictionary.`
    if(i == s.size()){
        res.insert(v);
        return;
    }

    string temp = "";

    for(int k = i ; k < s.size() ; k++){
        temp += s[k];
        if(st.find(temp) != st.end()){
        v.push_back(temp);
        helper(s, st, k+1);
        v.pop_back(); `//Backtracking to find more solution`
        }
    }
}

我的计算表明时间复杂度应该是 O(n^n)。

标签： c++stringrecursiontime-complexitybacktracking

解决方案

查看算法，最坏的情况类似于 IIII 试图在数组中找到组合：{I, I , I, I} 这意味着您从 I 开始，然后您需要检查三个 I，因此您需要第一个为 7，第二个为 7，所有这些为 7，所以想想你的问题，在最坏的情况下是 (2n-1)*n，所以在这种情况下，n 是 4，如果我们得到 28如果你想要大的 O 表示法需要计算，你会去 O(n^2) 不知道你是怎么得到 N^N 的......这是一个真正巨大的数字，只是说这令人惊讶......

推荐阅读