Если проблема сложности 2n^2 + n может быть решена за 24 единицы времени для n = 2, сколько времени занимает n = 4?Сложность для 2n^2 + n
Мне сказали, что ответ 48. Но я считаю, что это должно быть 24^2, потому что сложность алгоритма O(n^2).
Цените, если бы кто-нибудь мог просветить меня.
Я, конечно, не думаю, что это было бы 24^2. Поскольку вы говорите о O(n^2), и вам дается пример, который занимает 24 единицы времени для n = 2, из этого следует, что для n = 4 для завершения потребуется около 4 раз дольше (2^2 = 4; 4^2 = 16 - около 4 раз).
Если вы хотите вычислить его по-другому, подключите n = 2 к 2*n^2 + n, вы получите 10. Если 10 = 24 означает, что для каждого цикла требуется 2,4 единицы времени. Затем, подключив в n = 4 вы получаете 2*4^2 + 4 = 36 и умножения на 2.4 вы получите 86.4
Как и ответ Candide и bcorso, также ваш предполагает, что постоянный член в времени выполнения равен 0. –
@BorisStitnicky - мой ответ предполагает, что постоянный член равен 0, потому что выражение «2n^2 + n» не выражается в члены Big-O, что в данном случае было бы «n^2». Поэтому я предположил, что '2 * n^2 + n + 0' является явной вычислительной сложностью. –
Использование Ruby, как язык, математику, формула OP является
f = -> x { 2 * x ** 2 + x }
(1) Если предположить, что один шаг алгоритма занимает 1 единицу время, ответ 50, так как постоянный член c является
c = 24 - f.(2) #=> 10
# and
c + f.(4) #=> 50
в этом предположении, что ответ 50.
(2) Если, однако, мы даем один шаг алгоритма принимать e единиц времени вместо 1 единицу времени, то константа c будет:
24 - e * 10
и время работы для n == 4 будет
24 + e * 26 # gives 50 for e == 1
(3) При дополнительном предположении, что постоянное время равно нуль (то есть, данная формула точной), мы имеем
24 - e * 10 == 0
И ответы на Candide, bcorso и Milky Dinescu применяются.
Несмотря на то, что в вопросе ОП не указано, что 1 шаг == 1 единица времени, я все еще чувствую, что это было намерение автора, также основанное на типичном, легко проверяемом учебнике результата 50.
Постоянное время не может быть определено с помощью этого анализа, это может быть 4 или целый ряд значений. – Candide
Я отредактировал ответ, чтобы уточнить предположения. Я считаю, что тот факт, что я выбрал предположение (1), не является веской причиной для вас. –
Я не хотел быть грубым, это только то, что ваше предположение недействительно и, следовательно, компрометирует остальную часть аргумента. В больших обозначениях f (n) линейно зависит от фактического времени вычисления. Вы принимаете равенство, которое является более сильным утверждением, чем то, что означает большая нотация. Я удаляю downvote, так как это важно для вас, бит, не торопитесь, чтобы прочитать о большой нотации, и вы поймете, почему ваше помещение не подходит. – Candide
Большая нотация O представляет собой просто асимптотическое обозначение. Строго говоря, f (n) = O (n^2) означает, что существует A, B вещественных чисел и n0 целых чисел, таких, что An^2 < = f (n) < = Bn^2 при n> = n0.
Следовательно, сначала , если n < n0 Тенденция даже не должна следовать n^2. Во-вторых, при n> = n0 вы гарантируете только, что f (n) ограничено (как указано выше).Если вы хотите приблизить, то O (n^2) означает, что при больших n вы можете опустить младшие члены, f (n) -> 2n^2, однако при малых n это приведет к значительной ошибке.
В вашем случае у вас есть точная функциональная форма исполнения, f (n) = 2n^2 + 2, поэтому вы должны использовать его!
Предположим, каждый шаг требует времени T0 с постоянной времени С, то Т (п) = Т0 * (2n^2 + N) + C. Если С = 0, то:
Ваши первые два абзаца абсолютно правильны, и большой учебный материал. Тем не менее, пункт 3 вашего ответа - это выбор предположения, сделанный вами. Я считаю, что автор вопроса имел в виду гораздо более простой случай, когда 1 шаг просто занимает 1 единицу времени, а остальная часть - постоянная стоимость, также на основе аккуратного ответа на учебник по 50 в этом случае. Может быть, вы должны наказать OP за то, что не задали четко сформулированный вопрос. –
@BorisStitnicky Да, ты прав. Я обновил, чтобы упомянуть, что я принимаю нулевое постоянное время. – bcorso
Сложность O (f (n)) содержит все вычисления, которые принимают c * f (n) + d количество времени, где c и d являются константами. Если d = 0, то:
В случае, при п = 2 и сложность O (2n^2 + 2) составляет 24:
24 = (2 * 2^2 + 2) * с, следовательно, с = 24/10 = 2,4
Теперь вычислим при п = 4:
(2 * 4^2 + 4) * 2,4 = 36 * 2,4 = 86,4 единиц времени
Если d не является 0 c = (24-d)/10, а для n = 4 -
36 * (24-d)/10 + d = 86,4 + 0,9d
Таким образом, это невозможно, ответ будет 48, который дополнительно предполагает линейный алгоритм
:) Хорошо сделано.Спасибо – iraycd
Я уточнил предположения, что я против вас беру в свой ответ, и я думаю, что автор вопроса имел в виду 1 шаг = 1 единицу времени. –
@Candide Я согласен с вами в том, что ответ невозможно быть 48. –
Чем больше я думаю об этом, это действительно зависит от того, как долго он принимает при п = 0. – Candide