Парадокс между фактическим временем выполнения и сложностью времени выполнения

Question

Решение со сложностью O (N * M), где N - количество строк, а M - максимальная длина строки во входном векторе. Время выполнения для 101 теста: 92 мс.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        map <vector<int>, vector<int>> mp;
        for(int i=0;i<strs.size();i++){
            vector <int> dum(26);
            for(int j=0;j<strs[i].length();j++){
                dum[strs[i][j]-97]++;
            }
            mp[dum].push_back(i);
        }
        vector <vector<string>> out;
        for(auto i=mp.begin();i!=mp.end();i++){
            vector <string> dumS;
            for(auto j=i->second.begin();j!=i->second.end();j++){
                dumS.push_back(strs[*j]);
            }
            out.push_back(dumS);
        }
        return out;
    }
};

Решение со сложностью O (N M logM), где N - количество строк, а M - максимальная длина строки во входном векторе. Время выполнения для 101 теста: 80 мс.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        vector <string> strsCopy(strs.size());
        strsCopy = strs;
        vector <vector<string>> out;
        map <string,vector<int>> mp;
        for(int i=0;i<strs.size();i++){
            sort(strs[i].begin(),strs[i].end());
            mp[strs[i]].push_back(i);
        }
        for(auto i=mp.begin();i!=mp.end();i++){
            vector <string> dum;
            for(auto j=i->second.begin();j!=i->second.end();j++){
                dum.push_back(strsCopy[*j]);
            }
            out.push_back(dum);
        }
        return out;

    }
};

Answer 1

Используемые контрастные термины, а именно: Время выполнения и Сложность времени , не совпадают.

Первый - это мера времени, затраченного вашей программой на работать в единицах точности времени (наносекунды, микросекунды и т. д.), соответствующие функции для которых можно получить с помощью таких библиотек, как ctime и chrono в c++.

. относится к тренду во время выполнения, соответствующему размеру входных данных для вашей программы. Он следует асимптотически c границам сложности, при которых для изменяющегося размера ввода вы увидите разницу в масштабировании во время выполнения.

Для небольших входных размеров большинство алгоритмов не будут иметь заметного различия, но достаточно большие входные данные (часто включается в тестовые случаи) будет достаточно, чтобы проверить это.