Считается ли O (mn) «линейным» или «квадратичным» ростом?

24

Если бы у меня была функция с временной сложностью O ( mn ), где m и n - размеры двух ее входов, мы бы назвали ее временную сложность «линейной» (поскольку она линейна как по m, так и по n ) или «квадратичной» ( так как это продукт двух размеров)? Или что-то другое?

Мне кажется, что называть его «линейным» сбивает с толку, потому что O (m + n) также является линейным, но гораздо быстрее, но мне кажется, что называть его «квадратичным» также странно, потому что он линейный в каждой переменной в отдельности.

Mehrdad
источник
7
Важно сказать, линейный в чем . Если, например, у нас есть граф с ребрами и вершинами, является линейным по количеству ребер, но (потенциально) квадратичным по количеству вершин. n O ( m + n )mnO(m+n)
Рафаэль
3
Я думаю, что комментарий Рафаэля точен на. «Линейный» должен использоваться относительно чего-то, часто это размер ввода. Если вы перенося матрица является «линейным» , так как вход имеет размер . Если вы ищете вхождения строки из символов в строке из символов, не является линейной --- будет. O ( m n ) O ( m n ) n m O ( m n ) O ( m + n )m×nO(mn)O(mn)nmO(mn)O(m+n)
SamM
3
Я бы также согласился с комментарием @ Рафаэля, но в то же время нередко можно услышать, как люди говорят, что конкретная временная сложность является «линейной», без упоминания относительно чего. И в некоторых случаях это не имеет значения, например, O (m + n) является линейным по отношению ко всем входам, поэтому я бы не стал дважды думать о том, чтобы назвать его линейным, как SamM также делал выше. Но возникает вопрос: что, если вообще, делает O (mn) нелинейным?
Мердад
3
@Mehrdad: Я думаю, что базовая линия «соответствует размеру входных данных, при условии, что входные данные закодированы в виде двоичной строки (на магнитной ленте Тьюринга)». Этот входной размер является функцией и . SamM приводит хорошие примеры. мnm
Рафаэль
1
См. Также people.cis.ksu.edu/~rhowell/asymptotic.pdf относительно обозначений Ландау с несколькими переменными.
Йонас Кёлкер,

Ответы:

18

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

Питер Шор
источник
Что делает рассмотрение одного из и постоянным разумным? нмN
user2768
11

Чтобы пояснить обсуждение в комментариях, важно, что вы измеряете относительно роста.

Как упомянуто @Kaveh, не является линейным в обоих случаях одновременно, но является линейным, если один является константой, а другой растет.О(мN)

С другой стороны, скорее всего будет считаться линейным. Интуитивно понятно, что если удваивается, или удваивается, или даже если и удваиваются, не может более чем удвоиться. Это не верно для ; если и оба удваивают увеличиваются на 4. Именно поэтому во многих контекстах это время выполнения будет считаться квадратичным. Я приведу пример этого с совпадением строк в нескольких параграфах.м н м н м + н м н м н м нО(м+N)мNмNм+NмNмNмN

Но обычно, когда вы используете нотацию Big- , вы используете ее в отношении чего-то конкретного. Так как мы в основном теоретики, это, как правило, размер вклада в проблему.О

Давайте возьмем Matrix Addition, например. Добавление двух матриц занимает время. Но каждый элемент нашего ввода затрагивается только один раз, поэтому его обычно называют линейным. Другими словами, наш вход имеет размер , поэтому время работы является линейным по размеру входа.O ( m n ) O ( m n ) O ( m n )м×NО(мN)О(мN)О(мN)

Теперь давайте посмотрим на сопоставление строк - а именно, нам дана строка размера и строка размера и мы хотим посмотреть, есть ли вхождение строки меньшего размера в большей строке. Мы можем проверить это наивно за время; это обычно считается квадратичным. Зачем? Если и могут быть чем угодно, установите . Тогда наше время работы и наш вход имеет размер .n O ( m n ) m n m = n O ( m 2 ) 2 mмNО(мN)мNмзнак равноNО(м2)2м

С другой стороны, если мы используем алгоритм Рабина-Карпа , мы получаем (в среднем) времени. Наш вход состоял из обеих строк, поэтому мы также имели размер . Следовательно, это обычно называется линейным.O ( m + n )О(м+N)О(м+N)

Подводя итог: обычно называется линейным для таких вещей, как умножение матриц, потому что оно линейно по размеру входных данных, но обычно называется квадратичным для таких вещей, как сопоставление строк из-за меньшего входного значения. Какой термин подходит, зависит от контекста, в котором вы его используете.О(мN)

Samm
источник
8

Если вы измеряете время работы в , то O ( т п ) является не линейной функцией в ( т , п ) . Если между и нет связи, эта функция в целом может расти квадратично .(м,N)O(mn)(m,n)нmn

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

Кава
источник
3

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

Реза
источник
2
Может не быть доминирующей переменной, например, если у вас есть количество узлов и ребер.
Рафаэль
0

Учитывая некоторый язык и функция f такая, что min { | w 1 | , | w 2 | } f ( | w | ) для каждого вы можете оценить время работыL={w1#w2|wi(Σ{#}),}fмин{|вес1|,|вес2|}е(|вес|)O ( | w 1 || w 2 | )весзнак равновес1#вес2LО(|вес1||вес2|)алгоритм, который распознает как O ( f ( | w | ) ( | w | - f ( | w | ) ) = O ( f ( | w | ) | w | - f ( | w | ) 2 ) = O ( f ( | w | ) | w | ) .LО(е(|вес|)(|вес|-е(|вес|))знак равноО(е(|вес|)|вес|-е(|вес|)2)знак равноО(е(|вес|)|вес|)

Это означает, что вы получаете линейное время, если меньшая часть вашего ввода постоянна (относительно всего входа), что-то среднее (например, ), если это сублинейное и квадратичное время выполнения, если оно линейное.О(NжурналN)

frafl
источник