0

这是一种算法，计算一个字符串（search_word）在另一个（文本）中出现的字谜：

#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
using namespace std;

int main()
{
    string text = "forxxorfxdofr";
    string search_word = "for";
    deque<char> word;
    word.insert(word.begin(), text.begin(), text.begin() +  search_word.size());
    int ana_cnt = 0;

    for (int ix = 3; ix <= text.size(); ++ix)
    {   
            deque<char> temp = word;
            sort(word.begin(), word.end());
            if (string(word.begin(), word.end()) == search_word)
                    ++ana_cnt; 
            word = temp;    
            word.pop_front();
            word.push_back(text[ix]);
    }   
    cout << ana_cnt << endl;
}

这个算法的复杂度是多少？

我认为这是O(n)算法，n文本的长度在哪里。这是因为执行 for 循环内部所需的时间量与n. 然而，也有人认为不是O(n)。他们说排序算法在计算复杂度时也很重要。

4

1 回答 1

1

如果O(n)text您仅将具有长度的字符串n视为输入。

证明：您正在ix从3（可能search_word.size()，不是吗？）循环到text.size()，所以渐近地执行循环体n时间（因为循环体中没有break，continue或修改ix）。

循环体独立于n. 它对固定大小的队列进行排序，即m= search_word.size()，即O(m log(m))在平均情况下（最坏情况O(m^2)）。因为这是独立的，所以n我们总共完成了O(n).

不是O(n)：如果你想更精确一点，你可能会将search_word长度m作为输入来计算，在最坏的情况下，这会达到O(n m log(m))平均总数。O(n m^2)

于 2013-09-15T16:48:57.347 回答