int sum = 0;
for(int i = 1; i < n; i++) {
for(int j = 1; j < i * i; j++) {
if(j % i == 0) {
for(int k = 0; k < j; k++) {
sum++;
}
}
}
}
Я не понимаю, как, когда j = i, 2i, 3i ... последний for
цикл выполняется n раз. Думаю, я просто не понимаю, как мы пришли к такому выводу на основании if
заявления.
Редактировать: я знаю, как вычислить сложность для всех циклов, за исключением того, почему последний цикл выполняется i раз на основе оператора мод ... Я просто не вижу, как это я. В принципе, почему я не могу пойти на я * я, а не я?
for (j = i; j < i *i; j += i)
тогда вам не нужно проверять модуль (потому чтоj
гарантированно делится наi
).if
Заявления @ChristophBauer абсолютно не игнорируются. Этоif
утверждение означает, что сложность составляет O (n ^ 4) вместо O (n ^ 5), потому что это заставляет самый внутренний цикл выполнять толькоi
времена вместоi*i
времен для каждой итерации второго цикла.k < n^2
это O (n ^ 5), но знание (понимаяif
) предполагает O (n ^ 4).Ответы:
Давайте обозначим петли A, B и C:
j % i == 0
оценивается, что занимает O (1) время.Умножая все это вместе, мы получаем O ( n × i 2 × (1 + i )) = O ( n × i 3 ). Так как я в среднем O ( n ), это O ( n 4 ).
Хитрая часть этого говорит, что
if
условие верно только 1 / i времени:На самом деле,
j
доj < i * i
, а не только доj < i
. Но условиеj % i == 0
верно, если и только еслиj
кратноi
.В кратные
i
пределах являютсяi
,2*i
,3*i
...,(i-1) * i
. Они естьi - 1
, поэтому цикл C достигаетсяi - 1
раз, несмотря на то, что цикл B повторяетсяi * i - 1
.источник
if
условие занимает O (1) времени на каждую итерацию цикла B. Здесь преобладает цикл C, но я посчитал его выше, поэтому он просто «показывает мою работу».n
итерации.n*n
итерации. Представьте себе случай, когдаi=n
, тогдаj=n*n
.n
итерации, потому что он выполняется толькоi
раз, где в худшем случаеi
ограниченn
.Таким образом, сложность кода составляет O (n × n × n × n).
Я надеюсь, что это поможет вам понять.
источник
Все остальные ответы верны, я просто хочу изменить следующее. Я хотел посмотреть, было ли сокращение выполнения внутреннего k-цикла достаточным, чтобы уменьшить реальную сложность ниже.
O(n⁴).
Поэтому я написал следующее:После выполнения этого становится очевидно, что сложность на самом деле
n⁴
. Последние строки вывода выглядят так:Это показывает, что фактическая относительная разница между фактическим
n⁴
и сложностью этого сегмента кода является асимптотическим фактором к значению вокруг0.124...
(фактически 0,125). Хотя это не дает нам точное значение, мы можем вывести следующее:Сложность времени - это
n⁴/8 ~ f(n)
гдеf
ваша функция / метод.~
что предел двух сторон операнда равен. Или:(Я выбрал 363 как исключенную верхнюю границу, потому что
n = 362
это последнее значение, для которого мы получаем разумный результат. После этого мы превышаем длинное пространство и относительное значение становится отрицательным.)Пользователь kaya3 выяснил следующее:
источник
n⁴/8 + o(n⁴)
, но вn⁴/8 + O(n³)
любом случае можно дать более строгое выражение с большим О.Удалить
if
и по модулю без изменения сложностиВот оригинальный метод:
Если вас смущает
if
и по модулю, вы можете просто рефакторировать их,j
перепрыгивая прямо сi
на2*i
на3*i
...:Чтобы было еще проще рассчитать сложность, вы можете ввести посредника
j2
переменную, чтобы каждая переменная цикла увеличивалась на 1 на каждой итерации:Вы можете использовать отладку или старой школы
System.out.println
, чтобы проверить, чтоi, j, k
триплет всегда одинаков в каждом методе.Закрытое выражение формы
Как уже упоминалось другими, вы можете использовать тот факт, что сумма первых
n
целых равнаn * (n+1) / 2
(см. Треугольные числа ). Если вы используете это упрощение для каждого цикла, вы получите:Очевидно, что это не та же сложность, что и в исходном коде, но она возвращает те же значения.
Если вы гуглите первые термины, вы можете заметить, что они
0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731
появляются в «числах Стирлинга первого рода: s (n + 2, n)». , с двумя0
с добавлены в начале. Это означает, чтоsum
это число Стирлинга первого родаs(n, n-2)
.источник
Давайте посмотрим на первые две петли.
Первый простой, он цикличен от 1 до n. Второй интереснее. Это идет от 1 до я в квадрате. Давайте посмотрим несколько примеров:
В совокупности
i and j loops
есть1^2 + 2^2 + 3^2
.Существует формула для суммы первых n квадратов,
n * (n+1) * (2n + 1) / 6
, что примерноO(n^3)
.У вас есть последний,
k loop
который повторяется от 0 доj
тогда и только тогда, когдаj % i == 0
. Посколькуj
идет от 1 доi^2
,j % i == 0
верно дляi
раз. Так какi loop
повторяетсяn
, у вас есть один дополнительныйO(n)
.Так что у вас есть
O(n^3)
отi and j loops
и другойO(n)
изk loop
за большой общей сложностиO(n^4)
источник
j % i == 0
только когда j составляет 5, 10, 15, 20 и 25. 5 раз, как значение i. Если бы вы записали числа от 1 до 25 в квадрате 5 x 5, только 5-й столбец будет содержать числа, кратные 5. Это работает для любого числа i. Нарисуйте квадрат n на n, используя числа от 1 до n ^ 2. N-й столбец будет содержать числа, кратные n. У вас есть n строк, поэтому n чисел от 1 до n ^ 2 делится на n.i
попадании 5, поэтому вj
циклах от 1 до 25 вы не можете выбрать произвольное число. Если ваш 2-й цикл будет идти к фиксированному числу, например 24, вместо этогоi * i
, это будет постоянное число и не будет привязано к немуn
, так было быO(1)
. Если вы думаете оj < i * i
противj <= i * i
, это не будет иметь большого значения, так как будутn
иn-1
операции, но в нотации Биг-о, оба означаютO(n)