Big O Notation for Algorithm

Я не могу решить проблему; Кто-нибудь может мне помочь?Big O Notation for Algorithm

Что такое обозначение Big O для ниже утверждения: -

for (int i=2;i<=n;i=i*4) 
    sum++;

источник

2009-08-10 Anonymous

Это заявление является неполным. Где тело? – bdonlan

@ bdonlan: Если тело опущено, оно, вероятно, не влияет на сложность выполнения. –

@Charlie, если тело опущено, этот цикл примерно эквивалентен нулевому утверждению и, следовательно, O (1). Мы должны предполагать некоторую сложность для тела, даже если это тело = O (1). – bdonlan

После того, как я растет в геометрической прогрессии, то O (журнал (п)).

Если n в 16 раз больше, ожидается, что цикл будет выполняться только в два раза больше, чем это было бы.

источник

2009-08-10 02:37:38

, но проблема в том, что я начинаю с 2 и растет со временем 4. – 2009-08-10 02:39:22

Это не имеет значения для большой записи O. Оно растет как 4^i = n. 2 и 4 являются просто константами в этом случае. –

Сэмюэл прав. Число итераций - это ответ на этот вопрос: «Сколько раз нужно умножить на 4, чтобы превысить n?» Ответ: (плюс-минус 1, cuz «неаккуратно, нормально, когда вы делаете вычисление большого вывода!)) (Базовая база 4 из n/2), поэтому сложность является большой-O журнала (n)/log (4) - 1/2, что является O (log (n)). –

После того, как вы знаете, что начальная точка и множитель для i> 1, их точные значения не имеют значения с точки зрения большой-O (они только переводят в константы добавлены или умножения основного компонента, O(log N), и такие константы пренебрегали в рассуждениях с большими выводами - вот в конце концов, это все-таки логика !!!).

источник

2009-08-10 02:42:24

Попробуйте подсчитать количество циклов для нескольких (малых) значений n, а затем нарисуйте результат (n по горизонтальной оси, счетчик циклов по вертикальной оси). Игра с проблемой является большой, когда вы впервые учитесь.

В зависимости от того, какие значения вы выбрали для n, вы можете не видеть шаблон. Например, количество циклов одинаково для n = 10 и n = 20. Учитывая, когда число циклов изменится, также будет обнаружен шаблон, который может рассказать вам о большом времени.

После того, как вы лучше понимаете алгоритм синхронизации, вам не нужно проходить эту процедуру, требующую много времени. Вы сможете математически вычислять время O-O с помощью анализа кода.

источник

2009-08-10 02:42:40 outis

-1: Графические значения для малых n не говорят вам, что происходит при больших n, а O - о том, что происходит при больших n , –

эй, это действительно работоспособная идея. используйте калькулятор или компьютер, чтобы подсчитать количество итераций для малых, больших и чрезвычайно больших n, а затем график в линейном масштабе. – Midhat

Идея заключалась в том, чтобы научить OP ловить рыбу, а не давать рыбу. Основная проблема заключается в том, что мое предложение может привести к тому, что OP будет выбирать значения, которые слишком близки друг к другу, чтобы увидеть шаблон. – outis

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

Для двоичного поиска при увеличении размера n у вас есть операции log2 (n), чтобы найти значение. Поскольку число операций в терминах log, то O (log N) для двоичного поиска (где log log log 2).

Для чего у вас есть, у вас есть N количество операций (это даже если вы компенсируете), поскольку оно растет линейным образом, что является O (N). Это обозначение для линейного поиска, так как для определения значения может потребоваться n/2 опциона, это все равно O (N).

Я бы посмотрел Wikipedia on O(N) notation. У этого есть более техническое объяснение и более большая информация о нотации O.

источник

2009-08-10 03:03:40 Glenn

Хорошее общее объяснение, но это не особенно линейно: P Это 'O (log N)'. – Thorarin

Вы правы. Я вернулся и посмотрел на код, и я ошибся в добавлении. Вы правы, это O (log n) – Glenn

Спасибо, что указали это. – Glenn

Поскольку вы делаете это как упражнение по домашнему заданию, вам действительно нужно вернуться к первым принципам; т.е. математическое определение нотации O. Выясните, сколько простых шагов вычисления есть, поскольку «n» увеличивается, выработайте лимит алгебраически, а затем переходите к ответу.

На практике большинство людей оценивают сложность «O», основанную на знании классических примеров и опыта. И нередко они ошибаются.

источник

2009-08-10 03:10:28

Предполагая, что «сумма ++» является постоянной, что является довольно разумным предположением, алгоритм равен O (log _n).

Поскольку цикл идет от 2 до n, вы знаете, что оно не более O (n). Однако, поскольку ваш прирост умножается на 4 каждый цикл, экспоненциально меньше времени, проведенного в цикле.

источник

2009-08-10 03:42:57 Unknown

За исключением того, что нет записи log4 в O. Это просто журнал, база вытягивается как постоянная, а O-нотация не использует константы. –

@Loren: на самом деле это распространенное заблуждение людей, которые не изучали CS. Формальное описание нотации Big O не требует никаких требований к упрощению уравнения. См. Http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition. Это на самом деле, почему алгоритмы, такие как http: //en.wikipedia.org/wiki/Karatsuba_algorithm не делает общих упрощений, таких как тот, который вы описываете. – Unknown

Первые 4 значения я 2, 8, 32, 128, так что формула, которая показывает, сколько итераций, что петли будут проходить через это:

((журнал (п)/журнал (2))/2) +0,5

источник

2009-08-10 21:21:50

Big O Notation for Algorithm

ответ

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