Граф количество раз запускает цикл (Big O)

Я дал pseodocode заявление, как например:Граф количество раз запускает цикл (Big O)

function testFunc(B) 
    for j=1 to B.length-1 
    for i=1 to B.length-j 
     if(B[i-1] > B[i] 
     swap B[i-1] and B[i]

И я сказал, чтобы показать, что этот алгоритм работает в Big o O(n^2) time.

Так что я знаю, что первая для цикла работает n раз, потому что я считаю, что она включена. Я не уверен в остальной части строк, хотя бы второй для цикла запустил n-2 раз? Любая помощь приветствуется.

источник

2015-10-21 user3739406

Скажем, b.length (n) = 5, поэтому j = 1,2,3,4,5. Тогда It (для второго цикла), 1 <= 4, 2 <= 3, 3 <= 2, то он выходит, так как n = 5, что в 2 раза меньше, поэтому n-2 раза? – user3739406

Внутренний цикл работает с уменьшением количества раз. Посмотрите на конкретный пример. Если B.length было 10, тогда содержимое внутреннего цикла было бы выполнено 10 раз, затем 9 раз и так далее, до 1 раза.

Используя уравнение Гаусса из:

N (N + 1)/2

вы можете увидеть, что внутренний код будет выполняться 55 раз в этом примере. (10 (10 + 1)/2 = 55)

Итак, из этого следует, что в течение n раз оно выполняло бы n (n + 1)/2 раза. Это эквивалентно:

1/2 п^2 + 1/2 п

С точки зрения Big-О, со-efficients и меньшие значения п игнорируются, так что это эквивалентно O (п^2).

источник

2015-10-21 00:31:16

Если N = B.length, то внешний контур работает N-1 раз, а внутренний цикл проходит (N-1)+...+3+2+1 раза, в общей сложности (N-1) * (N/2) = N^2/2 - N/2 раза, что означает O(n^2).

источник

2015-10-21 00:31:33 Andreas

Каким образом внешний цикл выполняется n-1 раз? Есть ли разница между «execute» и «run». Мне был показан пример от ** i = 1 до array.length-1 **, и мне сказали, что это выполняется n раз. – user3739406

@ user3739406 Если 'array.length' равно 2, то это' i = 1 to 2-1' aka 'i = 1 to 1', поэтому он только петли один раз. – Andreas

Предположим, что B.length - 5 раз. Таким образом, внешний цикл будет выполняться 4 раза. На первой итерации по внешнему циклу внутренний цикл будет выполняться 4 раза; на второй итерации внутренний цикл будет выполняться 3 раза; 2 раза для третьей итерации; и 1 раз для четвертого.

Давайте закладывать результаты из геометрически:

AAAA 
AAA 
AA 
A

Каждый А представляет получение условной/свопа внутри вложенного цикла, и вы хотите знать, в общем, как многие там есть. простой способ сосчитать состоит в удвоении форму треугольника, чтобы произвести прямоугольник:

AAAAB 
AAABB 
AABBB 
ABBBB

, и вы можете быстро увидеть, что для треугольника, сторона длины N, есть N*(N-1)/2 потому, что они половина N*(N-1) прямоугольник состоит из A. Выполняя умножение и игнорируя масштабный коэффициент 1/2 (поскольку big-O не заботится о константах), мы видим, что существуют O (N^2) A.

источник

2015-10-21 00:45:55 pjs

Граф количество раз запускает цикл (Big O)

ответ

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