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

Question

这是一种计算一个字符串 (search_word) 在另一个字符串 (text) 中出现的变位词的算法:

#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)。他们说排序算法在计算复杂度时也很重要。

Answer 1

如果您只考虑长度为 n 的字符串 text 作为输入，它是 O(n)。

证明:您正在从 3(可能是 search_word.size()，不是吗？)到 ix 循环到 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)最坏的情况下。