Для каких значений m (в терминах n) O (m * n) лучше, чем O (n ^ 2) (и почему)? - PullRequest
Новая
       14

Для каких значений m (в терминах n) O (m * n) лучше, чем O (n ^ 2) (и почему)?

0 голосов
/ 08 июля 2019

Обычно я могу ответить на этот вопрос, используя графики на Desmos, но мне сложно понять, как представить эти графики для визуализации разницы в крутизне, особенно когда m стремится к n, а m выходит за пределы n.

Примером, в котором это может появиться, является «сравнение двух массивов, чтобы найти, есть ли дубликаты из первого массива во втором массиве». Здесь m и n - длины массивов. Если m и n равны, то сложность составляет n^2 для решения парного сравнения с вложенным циклом. Но если они неравны, является ли граф сложности «хуже», чем n^2? Я не могу понять, как построить график, чтобы проверить или даже выразить это математически.

Ответы [ 3 ]

1 голос
/ 08 июля 2019

n и m являются полностью независимыми переменными. Если бы m можно было бы выразить через n , то сложность была бы выражена исключительно через n .

Общий сценарий для независимых переменных n и m состоит в определении длины двух массивов произвольного размера.

Нет смысла сравнивать эти временные сложности вообще, потому что они относятся к взаимоисключающим классам проблем.

Используя ваш пример, O (m * n) определяет сложность одного возможного решения проблемы

сравнить два массива, чтобы найти, есть ли дубликаты из первого массива во втором массиве

Однако эти два массива по-прежнему имеют независимые длины, поэтому, даже если они оказываются равными в одном конкретном случае равными, нельзя утверждать, что алгоритм теперь O (n ^ 2) . n и m по-прежнему являются независимыми переменными, если в задаче явно не указано, что они имеют одинаковую длину.

Поскольку каждое возможное решение должно повторять каждый массив хотя бы один раз, и ни один массив не имеет постоянной длины, и ни одна длина не выражается через другую, не существует никакого возможного решения вышеупомянутой проблемы, сложность которой можно определить чисто в условия n , поэтому попытка рассуждать об относительной эффективности каждой сложности не имеет смысла.

1 голос
/ 08 июля 2019

Для любых заданных постоянных значений m и n мы не можем ничего сказать о том, какое из них будет быстрее. Это потому, что Big-O, по определению, применяется только тогда, когда значения стремятся к бесконечности. В дальнейшем я буду предполагать, что мы говорим о том, что происходит, когда значения стремятся к бесконечности.

Мы хотим знать, когда O(m*n) быстрее, чем O(n^2). Формальные определения Big-O проверяют либо f(n) <= k.g(n), либо f(n)/g(n). В любом случае, начиная с n > 0, легко видеть, что мы можем просто отменить один n из m*n и n^2 и получить эквивалентную проверку.

Итак, теперь мы хотим выяснить, когда O(m) быстрее, чем O(n), т. Е. m меньше n для каждого значения n за пределами некоторой точки.

На самом деле это то же самое, что сказать m = o(n), что является вашим ответом. Примечание: это little-O .

В менее абстрактных терминах m может быть любой функцией n "меньше" n (более чем на постоянный коэффициент). Вот несколько примеров:

  • m = 1 работает.
  • m = log n работает.
  • m = sqrt(n) работает.
  • m = n / 231689 не работает (отличается постоянным коэффициентом).
  • m = n - 9873054 не работает (отличается постоянным коэффициентом).
  • m = n^2 не работает (m растет быстрее).
1 голос
/ 08 июля 2019

Это полностью зависит от того, что m.Поскольку здесь речь идет о сложности времени, даже без построения графика вы можете сказать, что O (m*n) лучше, чем O(n^2), когда m <<code>n.Например, m может быть O(logn), O(n^(1/2)) и т. Д.

После того, как OP отредактировал вопрос:

Я поговорю о части compare two arrays to find if there are any duplicates from the first array in the second array.Пусть размер A будет m, размер B будет n. 

vector<int> find_duplicates(vector<int> A, vector<int> B){
    vector<int> duplicates;
    unordered_map<int, int> frequency;
    for(auto num: B){
        frequency[num]++;
    }
    for(auto num: A){
        if(frequency[num] > 0){
            duplicates.push_back(num);
            frequency[num]--;
        }
    }
    return duplicates;
}

for(auto num: B){...} имеет временную сложность O(n).for(auto num: A){...} имеет временную сложность O(m).Но m> n или m O(max(m,n)).

В этом решении O(max(m,n)) <<code>O(m*n).Надеюсь, это очистило ваши сомнения.

...