Улучшаем сложность

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
// функция возвращает true, если векторы из одинаковых элементов
// перепишите эту функцию, улучшив её асимптотическую сложность
bool TestPermut(const vector<int>& v1, const vector<int>& v2) {
    // если они разной длины, элементы заведомо разные
    if (v1.size() != v2.size()) {
        return false;
    }
 
    for (int i : v1) {
        // проверяем, что каждый элемент первого вектора
        // содержится одинаковое количество раз в обоих векторах
        if (count(v1.begin(), v1.end(), i) != count(v2.begin(), v2.end(), i)) {
            return false;
        }
    }
 
    return true;
}
 
int main() {
    int n;
    cin >> n;
    vector<int> v1, v2;
    v1.reserve(n);
    v2.reserve(n);
 
    for (int i = 0; i < n; ++i) {
        v1.push_back(rand());
        v2.push_back(rand());
    }
 
    // оба вектора случайны, вряд ли они совпадут
    cout << "Random vectors match? "s << flush;
    cout << (TestPermut(v1, v2) ? "Yes"s : "No"s) << endl;
 
    // делаем один перестановкой другого явным образом
    v2 = v1;
    random_shuffle(v2.begin(), v2.end());
    cout << "Permuted vectors match? "s << flush;
    cout << (TestPermut(v1, v2) ? "Yes"s : "No"s) << endl;
}

vector<int> v1_ = v1;
    vector<int> v2_ = v2;

bool TestPermut(const vector<int>& v1, const vector<int>& v2) {
    // если они разной длины, элементы заведомо разные   
    if (v1.size() != v2.size()) {
        return false;
    }
    //можно еще проверить, а не передали ли нам один и тот же вектор
 
    //Поскольку векторы переданы через const &, придётся сортировать копии.
    //    делаем копии
    auto tv1 = v1;
    auto tv2 = v2;
    
    //Если отсортировать векторы алгоритмом sort
    //    сортируем. Каждая сортировка - O(N·log(N))
    std::sort(tv1.begin(), tv1.end());
    std::sort(tv2.begin(), tv2.end());
    
    //они должны стать равными, иначе элементы в них различны.
    //    сравниваем два вектора. Сравнение - O(N)
    return tv1 == tv2;
}