Если бы у меня была функция с временной сложностью O ( mn ), где m и n - размеры двух ее входов, мы бы назвали ее временную сложность «линейной» (поскольку она линейна как по m, так и по n ) или «квадратичной» ( так как это продукт двух размеров)? Или что-то другое?
Мне кажется, что называть его «линейным» сбивает с толку, потому что O (m + n) также является линейным, но гораздо быстрее, но мне кажется, что называть его «квадратичным» также странно, потому что он линейный в каждой переменной в отдельности.
Ответы:
В математике такие функции называются полилинейными функциями. Но компьютерные ученые, вероятно, вообще не будут знать эту терминологию. Эту функцию определенно не следует называть линейной, ни в математике, ни в информатике, если только вы не можете разумно считать и константой.нм N
источник
Чтобы пояснить обсуждение в комментариях, важно, что вы измеряете относительно роста.
Как упомянуто @Kaveh, не является линейным в обоих случаях одновременно, но является линейным, если один является константой, а другой растет.O ( м н )
С другой стороны, скорее всего будет считаться линейным. Интуитивно понятно, что если удваивается, или удваивается, или даже если и удваиваются, не может более чем удвоиться. Это не верно для ; если и оба удваивают увеличиваются на 4. Именно поэтому во многих контекстах это время выполнения будет считаться квадратичным. Я приведу пример этого с совпадением строк в нескольких параграфах.м н м н м + н м н м н м нO ( m + n ) м N м N м + н м н м N м н
Но обычно, когда вы используете нотацию Big- , вы используете ее в отношении чего-то конкретного. Так как мы в основном теоретики, это, как правило, размер вклада в проблему.О
Давайте возьмем Matrix Addition, например. Добавление двух матриц занимает время. Но каждый элемент нашего ввода затрагивается только один раз, поэтому его обычно называют линейным. Другими словами, наш вход имеет размер , поэтому время работы является линейным по размеру входа.O ( m n ) O ( m n ) O ( m n )м × н O ( м н ) O ( м н ) O ( м н )
Теперь давайте посмотрим на сопоставление строк - а именно, нам дана строка размера и строка размера и мы хотим посмотреть, есть ли вхождение строки меньшего размера в большей строке. Мы можем проверить это наивно за время; это обычно считается квадратичным. Зачем? Если и могут быть чем угодно, установите . Тогда наше время работы и наш вход имеет размер .n O ( m n ) m n m = n O ( m 2 ) 2 mм N O ( м н ) м N m = n O ( м2) 2 м
С другой стороны, если мы используем алгоритм Рабина-Карпа , мы получаем (в среднем) времени. Наш вход состоял из обеих строк, поэтому мы также имели размер . Следовательно, это обычно называется линейным.O ( m + n )O ( m + n ) O ( m + n )
Подводя итог: обычно называется линейным для таких вещей, как умножение матриц, потому что оно линейно по размеру входных данных, но обычно называется квадратичным для таких вещей, как сопоставление строк из-за меньшего входного значения. Какой термин подходит, зависит от контекста, в котором вы его используете.O ( м н )
источник
Если вы измеряете время работы в , то O ( т п ) является не линейной функцией в ( т , п ) . Если между и нет связи, эта функция в целом может расти квадратично .( м , н ) O ( м н ) ( м , н ) нм N
Однако это линейная функция в каждой из них в отдельности, т.е. если вы фиксируете одну из них и смотрите на рост другой переменной, то это линейная функция в другой.
источник
Чтобы измерить сложность проблем с несколькими входами , можно найти доминантную переменную и затем связать другие входы на основе этой переменной. При таком подходе вы можете получить функцию сложности, основанную на одной переменной .
источник
Учитывая некоторый язык и функция f такая, что min { | w 1 | , | w 2 | } ≤ f ( | w | ) для каждого вы можете оценить время работыL = { ш1# w2| веся∈ ( Σ ∖ { # } )*, ... } е мин { | вес1| , | вес2| }≤f( | ш | ) O ( | w 1 | ⋅ | w 2 | )ш = ш1# w2∈ L O ( | ш1| ⋅ | вес2| ) алгоритм, который распознает как
O ( f ( | w | ) ⋅ ( | w | - f ( | w | ) ) = O ( f ( | w | ) | w | - f ( | w | ) 2 ) = O ( f ( | w | ) | w | ) .L O (f( | w | ) ⋅ ( | w | - f( | w | ) ) = O ( f( | ш | ) | ш | - ф( | ш | )2) = O ( f( | ш | ) | ш | )
Это означает, что вы получаете линейное время, если меньшая часть вашего ввода постоянна (относительно всего входа), что-то среднее (например, ), если это сублинейное и квадратичное время выполнения, если оно линейное.O (nlogн )
источник