Время внутренней внутренней вложенной петли

Question

void smiley (int n) { 

for (int i = 0; i < n * n; ++i) { 
    for (int k = 0; k < i; ++k) 
     System.out.println(”k = ” + k); 
    for (int j = n; j > 0; j--) 
     System.out.println(”j = ” + j); 
    } 
} 

Как вы можете видеть, существуют две внутренние петли и одна внешняя петля. Время выполнения для этого - n^4. Я получаю n * n делает это n^2, но как две внутренние петли составляют общее время выполнения n^4?

PS

Один подобный случай здесь, время его работы является n^2. Я тоже не понимаю. У него три петли?

void smiley (int n, int sum) { 
for (int i = 0; i < n * 100; ++i) { 
    for (int j = n; j > 0; j--) 
     sum++; 
    for (int k = 0; k < i; ++k) 
     sum++; 
    } 
} 

Answer 1

Время выполнения не зависит от количества контуров цикла, а от количества циклов кода. Поэтому, если цикл выполняется 100 раз и содержит внутренний цикл, выполняемый 100 раз, тогда внутренний цикл выполняется 10 000 раз.

Для 1-го случая внешний контур равен O (n^2), первый внутренний контур равен O (n^2 * n^2), второй внутренний цикл равен O (n^2 * n), поэтому полный порядок равен O (n^2 + n^4 + n^3), приведенному к O (n^4).

Для второго случая внешний контур равен O (n), первый внутренний контур O (n * n), второй внутренний цикл O (n * n), поэтому полный порядок равен O (n + n^2 + n^2), приведенное к O (n^2).

Answer 2

В первом примере первый внутренний цикл ограничена i который сам по себе ограничен n^2. Я подозреваю, что это может быть n^4, который вы ищете.

Answer 3

Что здесь происходит, N (N + N) = 2N^2. Таким образом, код имеет порядок 2N^2. Три вложенных цикла дадут N^3 время работы N (N (N)).

Answer 4

Для первого вы делаете итерацию (int i = 0; i < n * n; ++i), так что в основном n^2, все в порядке - вы знали это. В этом цикле вы повторяетесь для (int k = 0; k < i; ++k) ... в конечном счете, i здесь будет доходить до n*n (n^2). Таким образом, ваша сложность алгоритма уже о O(n^4):

overall complexity = 
    outer loop complexity: n^2 
    * 
    (
     1st inner loop complexity: up to n^2 
     + 
     2nd inner loop complexity: n 
    ) 

Вы не заботитесь столько о втором внутреннем цикле здесь, так как он просто добавляет «небольшое» количество операций по сравнению с тем, добавил первый контур (n^2 + n кадры примерно равны n^2, с точки зрения алгоритмической сложности).

---

О вашем втором куске коды:

overall complexity = 
    outer loop complexity: n 
    * 
    (
     1st inner loop complexity: n 
     + 
     2nd inner loop complexity: up to n 
    ) 

Который является O(n^2).

Answer 5

void smiley (int n) { 

for (int i = 0; i < n * n; ++i) { 
    for (int k = 0; k < i; ++k) 
     System.out.println(”k = ” + k); 
    for (int j = n; j > 0; j--) 
     System.out.println(”j = ” + j); 
    } 
} 

для г мы получим 0 ~ п^2 и для каждого значения я, мы также получаем K цикл от 0 до I и J от п до 0 , что мы получим

∑_(i=0)^(n^2)* (∑_(j=0)^(i^2)+ ∑_(k=0)^n) ≅ ∑_(i=0)^(n^2)* (∑_(j=0)^(i^2)) ≅∑_(i=0)^(n^2)* (∑_(j=0)^(n^2)) ≅ n^4 

для этого один:

void smiley (int n, int sum) { 
for (int i = 0; i < n * 100; ++i) { 
    for (int j = n; j > 0; j--) 
     sum++; 
    for (int k = 0; k < i; ++k) 
     sum++; 
    } 
} 

мы получим п * (п + п) = 2 * п^2 ~ = п^2, то есть означает, что мы просто caluate: цикл в цикле мы используем умножение; петля вдоль цикла, мы используем add; игнорировать постоянную часть.

может быть, вы можете посмотреть здесь: http://en.wikipedia.org/wiki/Time_complexity

Answer 6

реорганизовать петли так:

void smiley (int n) { 

for (int i = 0; i < n * n; i++) { 
    for (int k = i+1; k < n*n; k++); 
    for (int j = 0; j < n; j++); 
    } 
} 

Внешний цикл выполняется N2 раз. Для каждого цикла внешнего цикла первый внутренний цикл запускает N2-i. i = 0, k петлей N2-0; i = 1, k петлей N2-1; ...; i = N2-1, k петель 0 раз.

Так время, проведенное в N2-0 + n2-1 + ... + 0 = N2 * (0 + N2)/2 = N4/2

Второй внутренний цикл проще: J не зависят от i. i петли N2 раз, а j циклов N раз для каждого цикла i.

Время, затраченное на второй внутренней петле N2 * N = N3

Время работы, в зависимости от размера входного будет Т (N) = Н4/2 + N3

Но асимптотическое время было бы N4, удаляя любые константы и переменные малой мощности.