Какова сложность этого алгоритма?

Question

Вот алгоритм подсчета вхождений анаграмм одной строки (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 - это длина текста. Это связано с тем, что время, необходимое для выполнения цикла внутри цикла, не зависит от длины n. Однако некоторые считают, что это не O(n). Говорят, что алгоритм сортировки также учитывается при вычислительной сложности.

Answer 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) в худшем случае.