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 ++) {
сумма ++;
}
}
}
}
Я не понимаю, как, когда j = i, 2i, 3i... последний цикл for
выполняется n раз. Я думаю, я просто не понимаю, как мы пришли к такому выводу на основе заявления «если».
Редактировать: Я знаю, как вычислить сложность для всех циклов, за исключением того, почему последний цикл выполняется i раз на основе оператора мода... Я просто не понимаю, как это я. По сути, почему я не могу перейти на i * i, а не i?
Давайте обозначим петли A, B и C:
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 ++) {
сумма ++;
}
}
}
}
j% i == 0
, что занимает O (1) время.Умножая все это вместе, мы получаем O ( n & # 215; i 2 < / sup > & # 215; (1 + i )) = O ( n & # 215; i 3 < 3 / sup > > >). Поскольку i в среднем O ( n ), это O ( n 4 < / sup >).
Сложная часть этого говорит о том, что условие if
является истинным только 1 / i времени:
По сути, почему я не могу подняться на i * i, а не на i?
На самом деле, j
подходит к j < i * i
, а не только до j < я
. Но условие j% i == 0
верно тогда и только тогда, когда j
кратно i
.
Множители i
в пределах диапазона: i
, 2 * i
, 3 * i
, ..., (i-1) * i
. Их i - 1
, поэтому цикл C достигается i - 1
раз, несмотря на итерацию цикла B i * i - 1
раз.
n
.n * n
. Представьте себе случай, когда i = n
, затем j = n * n
.n
, потому что он выполняется только i
раз, где i
ограничен n
в худшем случае.Таким образом, сложность кода равна O (n & # 215; n & # 215; n & # 215; n).
Я надеюсь, что это поможет вам понять.
Все остальные ответы верны, я просто хочу изменить следующее.
Я хотел посмотреть, было ли достаточно уменьшения числа казней внутреннего k-петли, чтобы уменьшить фактическую сложность ниже O (n4).
Так я написал следующее:
для (int n = 1; n < 363; + + n) {
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) {
сумма ++;
}
}
}
}
длинный кубик = (длинный) Math.pow (n, 3);
длинный hypCubic = (длинный) Math.pow (n, 4) ;
двойной родственник = (двойной) (сумма / (двойной) hypCubic) ;
System.out.println ("n =" + n + ": итерации =" + сумма +
", n & # 179; =" + куб + ", n4 =" + hypCubic + ", rel =" + относительный) ;
}
После выполнения этого становится очевидным, что сложность на самом деле n4
. Последние строки вывода выглядят так:
n = 356: итерации = 1989000035, n & # 179; = 45118016, n4 = 16062013696, rel = 0,12383254507467704
n = 357: итерации = 2011495675, n & # 179; = 45499293, n4 = 16243247601, rel = 0,12383580700180696
n = 358: итерации = 2034181597, n & # 179; = 45882712, n4 = 16426010896, rel = 0,12383905075183874
n = 359: итерации = 2057058871, n & # 179; = 46268279, n4 = 16610312161, rel = 0,12384227647628734
n = 360: итерации = 2080128570, n & # 179; = 46656000, n4 = 16796160000, rel = 0,12384548432498857
n = 361: итерации = 2103391770, n & # 179; = 47045881, n4 = 16983563041, rel = 0,12384867444612208
n = 362: итерации = 2126849550, n & # 179; = 47437928, n4 = 17172529936, rel = 0,1238518469862343
Это показывает, что фактическая относительная разница между фактическим n4
и сложностью этого сегмента кода является асимптотическим фактором по отношению к значению около 0.124...
(на самом деле 0,125). Хотя это не дает нам точного значения, мы можем сделать вывод следующее:
Сложность времени - n4 / 8 ~ f (n)
, где f
- ваша функция / метод.
f равно g асимптотически
(Я выбрал 363 в качестве исключенной верхней границы, потому что n = 362
- это последнее значение, для которого мы получаем разумный результат. После этого мы превышаем длинное пространство, и относительное значение становится отрицательным.)
Пользователь kaya3 выяснил следующее:
Кстати, асимптотическая постоянная составляет ровно 1/8 = 0,125; [вот точная формула через Wolfram Alpha][1].
[1]: https://www.wolframalpha.com/input/?i = сумма + для + i +% 3D + 1 + к + n-1 + of + i + + i + +% 28i-1% 29 +% 2F + 2
Давайте посмотрим на первые два цикла.
Первый прост, он зацикливается от 1 до n. Второй интереснее. Это идет от 1 до я в квадрате. Давайте посмотрим некоторые примеры:
e.g. n = 4
i = 1
j loops from 1 to 1^2
i = 2
j loops from 1 to 2^2
i = 3
j loops from 1 to 3^2
В целом, i и j-петли
вместе имеют 1 ^ 2 + 2 ^ 2 + 3 ^ 2
.
Существует формула для суммы первых n квадратов, n * (n + 1) * (2n + 1) / 6
, что примерно равно O (n ^ 3)
.
У вас есть последний цикл k
, который переходит от 0 к j
тогда и только тогда, когда j% i == 0
. Поскольку j
переходит от 1 к i ^ 2
, j% i == 0
верно для i
раз. Поскольку i loop
итерации над n
, у вас есть еще один O (n)
.
Таким образом, у вас есть O (n ^ 3)
из i и j cloops
и еще O (n)
из k loop
для общего количества O (n ^ 4)
if
и по модулю, не меняя сложностиВот оригинальный метод:
public static long f(int n) {
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++;
}
}
}
}
return sum;
}
Если вас смущают «если» и по модулю, вы можете просто отбить их, с «j», прыгнув прямо от «i» к «2 i» к «3 i» ...:
public static long f2(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
for (int j = i; j < i * i; j = j + i) {
for (int k = 0; k < j; k++) {
sum++;
}
}
}
return sum;
}
Чтобы еще проще рассчитать сложность, вы можете ввести промежуточную переменную j2
, чтобы каждая переменная цикла увеличивалась на 1 на каждой итерации:
public static long f3(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
for (int j2 = 1; j2 < i; j2++) {
int j = j2 * i;
for (int k = 0; k < j; k++) {
sum++;
}
}
}
return sum;
}
Вы можете использовать отладку или старую школу System.out.println
, чтобы убедиться, что триплет i, j, k
всегда одинаков в каждом методе.
Как упоминалось другими, вы можете использовать тот факт, что сумма первых n
целых чисел равна n * (n + 1) / 2
(см. Треугольные числа). Если вы используете это упрощение для каждого цикла, вы получаете:
public static long f4(int n) {
return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}
Очевидно, что он не соответствует сложности исходного кода, но возвращает те же значения.
Если вы гуглите первые термины, вы можете заметить, что 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)
.