Простой расчет Big-O

Question

Я интуитивно понимаю, что два цикла for выполняют функцию O (n ^ 2), но что если циклы не связаны.Как это выражается

Например:

for(x = 1; x < t; x++)
    for(y = 1; y < z; y++)
            do something trivial
    end
end

является биг-о этого O (t * z)?или это O (n ^ 2) или это O (t ^ 2).Я всегда это упускал, но хотел бы знать сейчас.

Спасибо

Answer 1

Это O (t * z).Если у вас есть два вложенных цикла, каждый из которых выполняет n итераций, то у вас n ^ 2 из-за n * n:)

Это похоже на вычисление площади .. для каждого t вы повторяете z раз .. так что это интуитивно t * z..

Или вы можете представить себе счетчик внутри циклов .. сколько будет результат?

Answer 2

for(x = 1; x < t; x++)
    for(y = 1; y < z; y++)
            do something trivial
    end
end

Как написано, эти циклы выполняются (t-1)*(z-1) = t*z - t - z + 1 times -> O(t*z)

Answer 3

По сути, это действительно O (t * z), но если в проблеме нет ничего конкретного, вы обычно просто говорите O (n ^ 2). Причина этого довольно проста: предположим, что у вас есть t, z с t & ne; z. Тогда для любого конкретного t, z существует t / z, который является константой. Вы можете выделить это, оно станет константой в выражении, и у вас будет n ^ 2. O (n ^ 2) - это то же самое, что O (t ^ 2) для наших целей - немного правильнее было бы сказать O (t ^ 2), но большинство людей поймут, что вы используете родовой n.

Обновление

Хорошо, извините, давайте продолжим. Нам даны t, z, как положительные натуральные числа с t & ne; z, так и без какой-либо конкретной функциональной связи между t и z. (Да, может быть таким отношением, но оно не в формулировке проблемы. Если мы не можем сделать такое предположение, то на проблему нельзя ответить: рассмотрим, например, что z = t ^x . Мы не знаем x , поэтому мы никогда не можем сказать, каким будет время выполнения. 1017 * z = s ^t . Если я могу утверждать, что функциональное отношение может существовать, то ответ неопределен.)

Теперь при рассмотрении мы можем видеть, что это будет O (t * z). Вызовите функцию, которая является реальным временем выполнения f (n) = n ² . По определению O (f (tz)) означает время выполнения f (tz) & le; кг (тс) для некоторой константы k> 0. Разделите на z. Тогда f (t) / z & le; (к / з) г (т) и, следовательно, f (т) & le; кг (т) . Подставляем и получаем f (t) = t ² , а переименование переменной дает O (n ² ) .

Answer 4

Я не знаю, что я рассмотрел бы это O (n ^ 2) без какой-либо дополнительной информации о том, как будет использоваться цикл.

Если z всегда будет меньше или равно 1, вы получите O (n) или O (1).

Answer 5

Обычно два цикла внутри друг друга - это O (n ^ 2), которое читается как O n squared.