Big O нотации, сложность

Так мы только начинаем Big O нотации, и у нас есть вопрос с просьбой это:Big O нотации, сложность

Что самое худшее время сложность для следующего цикла, если someWork имеет сложность O(i), отметив, что это означает, что i является счетчиком цикла, так что шаги someWork увеличивается каждый раз, когда счетчик делает:

while(i < n) 
    someWork(...) 
    i <-- i + 2

Это, очевидно, написано в псевдокоде, и я получил более легкие вопросы, так что я не верю У меня проблема с пониманием вопроса, это именно тот, который я застрял на. Могу ли я получить помощь, пожалуйста?

Большое спасибо!

источник

2014-01-15 Auxilio

предположим, что n - большое положительное целое число, а i равно 0. поэтому цикл может продолжаться в течение n/2 раз, так как i увеличивается на 2 каждый раз. – Santhosh

Хорошо, например, первый вопрос: «Какова наихудшая временная сложность этого цикла, если« someWork »является алгоритмом« O (1) »? Это последний вопрос в серии вопросов, которые увеличились в трудности Я получил ответ «O (n/2)» – Auxilio

Если ответ O (n/2), это означает, что 'someWork()' не имеет сложности O (i), но O (1). Дело в том, что O (n/2) в значительной степени означает O (n). –

Учитывая, что someWork() зависит от i и i есть, в среднем, примерно n/2 над все итерации внешнего цикла, временная сложность поэтому O(n²).

Это потому, что внешний контур зависит от n и someWork() («внутренняя петля» некоторого описания) также зависит от n.

Обоснование someWork() является O(n) следующим образом.

Скажем, n - 8. Это означает, что i принимает значения {0, 2, 4, 6}, в среднем 12/4 == 3.

Теперь давайте говорить n 16. Это означает, что i принимает значения {0, 2, 4, 6, 8, 10, 12, 14}, в среднем 56/8 == 7.

Предположим, что n - 32. Это означает, что i принимает значения {0, 2, 4, ..., 28, 30}, в среднем 240/16 == 15.

Если вы продолжаете, вы обнаружите, что количество операций, выполняемых someWork(), всегда n/2 - 1, следовательно O(n).

То, что в сочетании с самой петлей O(n), дает вам сложность O(n²).

источник

2014-01-15 03:36:43 paxdiablo

Мне это нравится, но мы не ищем среднего, мы ищем худший случай. В этом случае это одно и то же? Извините ... первый раз действительно работает с обозначением O. – Auxilio

@ Ауксилио, не делайте ошибки, думая, что мое использование слова «средний» относится к сложности. Я использую среднее значение, чтобы показать, что функция 'someWork()' зависит от 'n'. Это похоже на '1 + 2 + 3 + 4 + 5 = 3 * 5' (среднее число по числу),' 1 + 2 + 3 = 2 * 3', 1 + 2 + ... + n = (n + 1)/2 * n'. – paxdiablo

Вот и все! Спасибо! – Auxilio

Это действительно зависит от сложности someWork(). Если someWork() имеет петлю (или вложенные петли) внутри, сложность будет автоматически переходить от O (n) к O (n^2) или более. Если у SomeWork нет циклов, этот код имеет сложность O (n). Кстати, мне трудно понять эту последнюю строку. Это часть цикла? Приписывает ли я что-либо i (опечатка я имею в виду)?

источник

2014-01-15 03:28:47 dotNET

Это не обязательно будет идти от O (n) до O (n^2), если существует цикл вложенных циклов. Что, если вложенный цикл цикла повторяется над пустым списком? Его псевдокод не достаточен –

@ TheInternet: Сложности не заботятся о лучших случаях е сценариев. Обычно это имеет среднее и худшее время. См. Http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1. – dotNET

Сам псевдокод может быть недостаточным, но в тексте четко указано, что someWork - это O (i), который является эффективным O (n) в этом сценарии. Я проголосовал бы за это, за исключением того, что dotNET, похоже, упустил тот факт, что определенная сложность someWork была указана. – paxdiablo

упрощать вопрос немного, предположим, что последняя строка заменяется я < --- я + 1 так, что вы не пропуская значения i. Теперь, сколько работы сделано? Общее количество:

O (1) + O (2) + O (3) + O (4) + ... + O (n-1) + O (n) = O (1 + 2 + ... + n) = O (n (n + 1)/2) = O (n^2).

Теперь, в вашей проблеме, мы оставляем все четные значения i, что совпадает с удалением половины условий.Не должно быть слишком сложно понять, что это должно быть связано с чем-то, что составляет примерно 1/2 столько же операций, поэтому мы получаем O (n^2/2) = O (n^2).

источник

2014-01-15 07:22:48

Big O нотации, сложность

ответ

Смежные вопросы