В большой записи о временной сложности алгоритмического анализа, когда алгоритм зависит от n и k, в чем разница между этими двумя обозначениями. Также помощь PLS в нотации использовать, если есть вложенный цикл с внешним циклом, выполняющимся n раз, а внутренний цикл работает k раз?В чем разница между O (nk) и O (n + k) во временной сложности?
O (nk) означает, что время, которое требуется, пропорционально n * k. O (n + k) означает, что время, которое требуется, пропорционально n + k. Это как раз то, что кажется. Вы должны быть более конкретными в своем вопросе о том, что вы не понимаете.
В вашем случае время выполнения алгоритма равно O (nk), поскольку внутренний цикл выполняет в общей сложности n * k раз.
Должно быть ясно, что они отличаются, так как, например, если п = к:
О (пк) = O (пп) = O (N^2)
О (п + к) = O (2n) = о (п)
Спасибо .. если случай O (n + k), как будет цикл быть? Является ли это вложенным циклом или двумя циклами в строке. –
O (n + k) отражает общее время работы двух последовательных циклов, а не вложенных циклов, где первый имеет n итераций, а второй цикл имеет k итераций , – chepner
говорят, что функция F (п) является о (г (п)) означает, что существует некоторая константа д такая, что для всех значений п которые не менее одного, f (n) будет не больше q g (n).
И наоборот, говоря, что функция Р (х, у) является О (г (х, у)) означает, что существует некоторая константа д такая, что для всех значений х и у который не менее одного, f (x, y) будет не больше qg (x, y).
Если к является постоянной, то оба значения выше эквивалентны O (N), так как при любом значении K, и для любого п которого не меньше, чем один, если положить д равна (к + 1), то ни пк, ни п + к не превысит дп [т.е. (k + 1) n] для любого значения n, который не менее одного.
Если к и п являются полностью независимыми переменными, то О (пк) неприводимо; O (n + k) будет O (max (n, k)), так как если один устанавливает q, равный 2, q (max (n, k)) [т.е. 2max (n, k)] будет больше или равно n + k для всех значений n и k, которые не менее одного.
В этом случае я не думаю, что k принято как константа. – Daniel
Даже в случае полностью независимых переменных сложность оставалась бы O (n + k). Ваше объяснение неверно и абсурдно в последнем абзаце! Это не будет O (max (n + k)), поскольку две несвязанные переменные не могут сравниваться для максимального значения !!! –
@shekharsuman: Исправлено в O (max (n, k)). Почему нельзя сравнивать две несвязанные переменные для максимального значения? Функция max (x, y) равна x при x> = y и равна y при y> = x. – supercat
О (п + к) указывает на линейную скорость роста в большей из п или к. Предположим, что n больше.Тогда
n + k <= n + n = 2n = O(n)
Если п меньше, хотя, затем
n + k <= k + k = 2k = O(k).
ли или нет п тем больше, это всегда верно, что
n + k = O(n+k)
так это обозначение помогает скрыть эту неопределенность. Такая двухинтенсивная нотация полезна для алгоритмов графа, используя n для количества вершин и m для количества ребер. Вы можете написать одно выражение O (n + m), чтобы указать, что алгоритм O (n) для разреженных графов (m = Theta (n)), но медленнее для более плотных графов (например, O (n^2), если m = Theta (n^2)).
Для второго вопроса это просто простая арифметика. Вы повторяете внутренний цикл k раз на первой итерации внешнего цикла, k раз для второго и т. Д., Для общего количества операций k + k + ... + k = n * k, что является O (nk).
Это не линейный рост в больших n и k. Это линейный рост как n, так и k. Если n больше k, но k увеличивается, время выполнения алгоритма все равно растет линейно с k. – Daniel
Ну, вы можете полностью игнорировать «k», пока k = O (n). Только тогда, когда k = omega (n), O (n) и O (n + k) означают разные вещи. – chepner
(я имею в виду алгоритмический анализ, хотя «n» и «k» являются «фиксированными» в том смысле, что они описывают ввод конкретного алгоритма, а O (n + k) описывает время работы алгоритм на входе такого размера. Моя интерпретация, вероятно, не очень хорошо держится в более чисто математическом смысле обозначений.) – chepner
O (п):
for(i=0; i<n; i++) {
for(j=0; j<k; j++)
{}
}
O (п + к):
for(i=0; i<n; i++)
{}
for(j=0; j<k; j++)
{}
У вас есть +1 для лучшего объяснения ... –
На современных компиляторах я бы ожидал, что оба они будут O (1);) – user4235730
@ user4235730 ну, это в значительной степени зависит от типов i и j :-) –
Спасибо .. Я хотел бы знать, если O (пк) такая же, как О (п * к) .. –
@GobiKrishnan O (nk) - это то же самое, что и O (n * k). Это всего лишь два разных способа написания умножения ..., – Daniel