C++ сортировка векторов сложность времени

Question

Предположим, у меня есть vector<vector<int>> L с N векторами, а общее число int s суммировано по всем векторам не более M. Какова самая сложная временная сложность стандартной сортировки по C++ sort(L.begin(), L.end())?

Функция сравнения 10 имеет время выполнения не более O (M), поэтому очевидной оценкой является O (NM log N). Но если мы реализуем стандартный mergesort, мы можем видеть, что на каждом из уровней O (log N) не более чем на O (M) выполняется целочисленное сравнение, поэтому среда выполнения O ((N + M) log N). Это связано с тем, что при сравнении двух векторов длины A и B происходит время O (min (A, B)).

Является ли стандарт C++ гарантией того, что время выполнения O ((N + M) log N)?

Answer 1

Информация не достаточна. Вам также необходимо знать распределение значений M через векторы N. Если у вас есть что, то это прямо вперед, чтобы найти общую сложность:

1. std::sort имеет сложность O(N·log(N)) сравнений.

2. std::vector использует std::lexicographical_compare(v1, v2) для сравнения, что имеет сложность в сравнении O(min(v1.size(), v2.size())).

3. int сравнение имеет сложность O(1).

4. Дадим E(M, N) функция на M, N, что возвращает значит количество минимальных элементов между каждой парой внутренних векторов.

   • Например, если у вас есть равномерное распределение, это тривиальным равно M/N.
5. Возьмите продукт: Big Oh = N·log(N)·E(M, N)·1.
   • Для равномерное распределение, это будет M·log(N).

Вы можете использовать Discrete Probability Distribution theory, чтобы выяснить, что функция E(M, N) для любого распределения M через N.

---

Edit 1: Для того, чтобы управлять точкой как/почему это важно: Рассмотрим распределение, всегда делает мои векторы выглядеть следующим образом:

outer[0].size() == 1, 
outer[1].size() == 1, 
outer[2].size() == 1, 
..., 
outer[M-1].size() == (M - N + 1) 

В этом случае, E(M, N) = 1, потому что std::lexicographical_compare будет иметь только один другой элемент для сравнения с любой парой элементов. Таким образом, для этого конкретного распределения я буду всегда имеют сложность O(N·log(N)). Но с равномерным распределением у меня будет O(M·log(N)).

---

Edit 2: После комментария вы задаете распределение, давайте попробуем найти E(M, N).

Во-первых, обратите внимание, что в общей сложности T = (N choose 2) = N(N - 1)(1/2) различных комбинаций векторных сравнений.

Одна (и только одна) комбинация будет принимать X = O((M - N + 2)(1/2)) сравнения и имеет вероятность P(X) = 1/T.

Для сравнения любая другая комбинация требует только 1 сравнения (O(1)), и поэтому эти случаи происходят с вероятностью P(1) = (T - 1)/T.

Найти среднее просто: X·P(X) + 1·P(1).

Учитывая это, WolframAlpha говорит: E(M, N) = (M + (N - 2) N)/((N - 1) N).

Умножив эту функцию N log(N) дает нам (M + (N - 2) N) log(N)/(N - 1), что может быть еще более упрощена в Большой Ах вы ищете: O((M/N + N) log(N)).

Answer 2

В случае, если ваш Целые более или менее случайный¹⁾, большинство сравнений нужно только сравнить несколько первые числа каждого вектора (до первого несовпадения), поэтому на практике/в среднем

M (парадоксально) не оказывает никакого влияния на алгоритмической сложности

Чтобы дать вам некоторое представление: Даже, если ваши векторы имеют бесконечную длину и наиболее часто встречающееся число есть вероятность p 50%, вам нужно менее 2 сравнений в среднем на:

k < ∑ i*p^i = p/(1-p)^2 | p=0.5 
k < ∑ i*0.5^i = 2; 

Для других вероятностей результаты:

60% -> k < 2.5 
70% -> k < 3.4 
80% -> k < 5.0 
90% -> k < 10.0 

Имейте в виду, что все эти цифры верхние границы для среднее число целочисленных сравнений и независимых количества элементов в векторе

¹⁾ Случайно я не имею в виду случайное в криптографическом смысле. Цифры даже не должны проходить большинство качественных тестов для случайных чисел. Единственное требование состоит в том, что они не образуют один и тот же префикс - который растет с длиной вектора - систематически.
За исключением вредоносного ввода В настоящее время я не могу представить себе реалистический пример, который не квалифицировался бы как «более или менее случайный», но, вероятно, что-то еще.