Большая сложность простого не всегда линейного?

Question

Я уверен, что большинство из вас знает, что вложенный цикл имеет сложность O (n ^ 2), если входной размер функции равен n

for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
...
}
}

Я думаю, что это похоже на аналогичный аргумент, но я не уверен, что кто-нибудь может подтвердить?

for(int i = 0, max = n*n; i < max; i++{
...
}

Если это так, я предполагаю, что есть некоторые виды кода, чье отображение O не сразу очевидно, кроме рекурсии и подпрограмм.

Answer 1

Ваш простой простой цикл всегда O (m), где m - верхняя граница итераций. Но твой m действительно n * n, так что это O (n ^ 2).

Answer 2

Если m = n ^ 2, то «простое для», безусловно, линейно по m. Если вы хотите утверждать, что это n ^ 2, пожалуйста, продолжайте.

Здесь обозначение Big-O подсчитывает операции. Если вы выполняете n ^ 2 из них, я не уверен, что вам сообщит сумма в n ^ 2, потому что вы выполняете m операций.

Ваше предложение не имеет смысла для меня. Это вводит в заблуждение об истинном названии этой суммы. Правильный способ сказать, что это O (м).

Answer 3

Зависит от того, что вы подразумеваете под «простым». Поиск деления на два в отсортированном массиве размера n также может быть записан как не вложенный цикл for, но он будет иметь время O (log (n)). И, как вы правильно сказали, цикл for от 0 до n n будет выполняться за O (n n) времени.

Да, есть коды, где время работы не сразу очевидно. Более того, есть код, в котором эффект и даже цель не сразу очевидны:)

Answer 4

Это все еще O (n) - за исключением того, что ваш «n» в этом случае - «n * n». Вы просто увеличили значение n, а не сложность цикла.