Может ли алгоритм O (n) превышать O (n ^ 2) с точки зрения времени вычисления?

Предположим, у меня есть два алгоритма:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

Это естественно O(n^2). Предположим, что у меня также есть:

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

Это O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

Кажется, что хотя мой второй алгоритм O(n), это займет больше времени. Может ли кто-то расширить это? Я поднимаю его, потому что часто вижу алгоритмы, где они, например, выполняют первый шаг сортировки или что-то в этом роде, а при определении общей сложности - это самый сложный элемент, который ограничивает алгоритм.

Ответ 1

На самом деле big-O - это только верхняя граница, то есть вы можете сказать, что алгоритм O(1) (или действительно любой алгоритм, принимающий O(n²) или меньше времени) принимает O(n²). С этой целью переходим к нотации Big-Theta (Θ), которая является лишь жесткой привязкой. Подробнее см. формальные определения.

Если вы знаете только о большом-O, возможно, вам (неправильно) научили, что Big-O тесно связан. Если это так, вы, вероятно, можете просто предположить, что большая-тета означает то, чему вас научили большие средства O.

Я останусь в этом ответе, предположим, что вы спросили о (или подразумеваемом) большой-тете, а не о-о-о. Если нет, как уже упоминалось, если говорить о big-O, это скорее будет ситуация "все идет" - O(n) может быть быстрее, O(n²) можно быстрее или они могут принимать одинаковое количество (асимптотически) - обычно не удается сделать особо значимых выводов относительно сопоставления алгоритмов больших О, можно только сказать, что, учитывая большой-O некоторого алгоритма, этот алгоритм не будет занимать больше времени, чем это количество времени (асимптотически).

Асимптотическая сложность (которая представляет собой представление как big-O, так и big-Theta) полностью игнорирует задействованные постоянные факторы - она предназначена только для указания того, как время работы изменится по мере увеличения размера ввода.

Таким образом, конечно, возможно, что алгоритм Θ(n) может занимать дольше, чем Θ(n²) один для некоторого заданного n - который будет n, это будет действительно зависеть от используемых алгоритмов - для вашего конкретного примера, это будет иметь место для n < 100, игнорируя возможность оптимизации, отличающуюся между ними.

Для любых двух заданных алгоритмов, принимающих Θ(n) и Θ(n²) время соответственно, то, что вы, вероятно, увидите, это либо:

Алгоритм Θ(n) медленнее, когда n невелик, тогда Θ(n²) становится медленнее, так как n увеличивается (что происходит, если Θ(n) один более сложный, т.е. имеет более высокие постоянные множители) или
Θ(n²) один всегда медленнее.

Хотя возможно, что алгоритм Θ(n) может быть медленнее, тогда Θ(n²) один, затем Θ(n) один и т.д. как n увеличивается, пока n не станет очень большим, из с которого начинается Θ(n²), всегда будет медленнее, хотя это вряд ли произойдет.

Чтобы выразить это в несколько более математических терминах:

Предположим, что алгоритм Θ(n²) выполняет операции cn² для некоторого c.

И алгоритм Θ(n) выполняет операции dn для некоторого d.

Это соответствует формальному определению, поскольку мы можем считать, что это выполняется для n больше 0 (т.е. для всех n) и что две функции, между которыми время работы лежит, одинаковы.

В соответствии с вашим примером, если вы скажете c = 1 и d = 100, тогда алгоритм Θ(n) будет медленнее до n = 100, после чего алгоритм Θ(n²) станет медленнее.

_{(любезно предоставлено WolframAlpha).}

Ответ 2

Да, алгоритм O (n) может превышать алгоритм O (n ²) с точки зрения времени выполнения. Это происходит, когда постоянный множитель (который мы опускаем в большой записи O) является большим. Например, в вашем коде выше алгоритм O (n) будет иметь большой постоянный коэффициент. Таким образом, он будет работать хуже, чем алгоритм, который работает в O (n ²) для n < 10.

Здесь n = 100 - точка пересечения. Поэтому, когда задача может выполняться как в O (n), так и в O (n ²), а постоянный коэффициент линейного алгоритма больше, чем для квадратичного алгоритма, то мы склонны предпочитать алгоритм с худшим временем работы. Например, при сортировке массива мы переключаемся на сортировку вставки для меньших массивов, даже если сортировка слияния или быстрый сортировка выполняются асимптотически быстрее. Это связано с тем, что сортировка вставки имеет меньший постоянный коэффициент, чем слияние/быстрая сортировка и будет работать быстрее.

Ответ 3

Большие O(n) не предназначены для сравнения относительной скорости работы с другим алгоритмом. Они предназначены для измерения того, как быстро увеличивается время работы при увеличении размера ввода. Например,

O(n) означает, что если n, умноженное на 1000, тогда время работы примерно умножается на 1000.
O(n^2) означает, что если n умножается на 1000, то операция примерно умножается на 1000000.

Поэтому, когда n достаточно велико, любой алгоритм O(n) будет бить алгоритм O(n^2). Это не означает, что что-либо для фиксированного n.

Ответ 4

Короче говоря, да, это возможно. Определение O основывается на том факте, что O(f(x)) < O(g(x)) подразумевает, что g(x) окончательно займет больше времени, чем f(x), если будет достаточно большой x.

Например, известен факт, что при малых значениях сортировка слияния превосходит сортировку вставки (если я правильно помню, это должно быть верно для n меньше 31)

Ответ 5

Да. O() означает только асимптотическую сложность. Линейный алгоритм может быть медленнее, чем квадратичный, если он имеет такую же большую константу линейного замедления (т.е. Если ядро цикла работает в 10 раз дольше, оно будет медленнее, чем его квадратичная версия).

Обозначение O() - это только экстраполяция, хотя и довольно хорошая.

Ответ 6

Единственная гарантия, которую вы получаете, заключается в том, что - независимо от постоянных факторов - для достаточно больших n алгоритм O (n) будет проводить меньше операций, чем O (n ^ 2).

В качестве примера, позвольте считать операции в OPs аккуратном примере. Его два алгоритма отличаются только одной строкой:

for (int i = 0; i < n; i++) {       (* A, the O(n*n) algorithm. *)

против.

for (int i = 0; i < 100; i++) {     (* B, the O(n) algorithm. *)

Так как остальные его программы одинаковы, разница в фактическом времени работы будет определяться этими двумя строками.

Для n = 100 обе строки выполняют 100 итераций, поэтому A и B выполняют точно то же самое при n = 100.
Для n < 100, скажем, n = 10, A выполняет только 10 итераций, тогда как B составляет 100. Ясно, что A быстрее.
При n > 100, скажем, n = 1000. Теперь цикл A выполняет 1000 итераций, тогда как в петле B все еще фиксируются 100 итераций. Ясно, что А медленнее.

Конечно, сколько больших n нужно для ускорения алгоритма O (n), зависит от постоянного фактора. Если вы измените константу 100 на 1000 в B, то обрезание также изменится на 1000.