Какова временная сложность данного кода - PullRequest
Новая
       2

Какова временная сложность данного кода

1 голос
/ 24 января 2020

Я хочу знать временную сложность прилагаемого кода. Я получаю O (n ^ 2logn), в то время как мои друзья получают O (nlogn) и O (n ^ 2).

SomeMethod () = log n Вот код: 

j = i**2;
for (k = 0; k < j; k++) {
    for (p = 0; p < j; p++) {
        x += p;
    }
    someMethod();
}

enter image description here

Ответы [ 2 ]

2 голосов
/ 24 января 2020

Вопрос о переменной N не очень понятен, а выражение i**2.

i**2 дает ошибку компиляции в java.

при условии, что someMethod() занимает log N время (как указано в вопросе), и полностью игнорируя значение N,

позволяет вызывать i**2 как Z

someMethod(); работает Z раз. а временная сложность метода равна log N, поэтому становится:

Z * log N --------------------------- -------------- A

давайте назовем это выражение A.

Теперь x+=p выполняется Z ^ 2 раза (i l oop * j l oop) и требует постоянного времени для запуска. это дает следующее выражение:

( Z^2 ) * 1 = ( Z^2 ) ---------------------- B

давайте назовем это выражение B.

Общее время выполнения представляет собой сумму выражения A и выражения B. что приводит нас к:

O((Z * log N) + (Z^2))

, где Z = i**2

, поэтому окончательное выражение будет O(((i**2) * log N) + ((i**2)^2))

, если мы можем принять i**2 is i^2, выражение становится,

O(((i^2) * log N) + (i^4))

Учитывая только переменные высшего порядка, как мы рассматриваем n^2 в n^2 + 2n + 5, сложность может быть выражена следующим образом ,

i^4

0 голосов
/ 24 января 2020

Исходя из рисунка, сложность O (logNI 2 + I 4 ).

Мы не можем дать класс сложности с одной переменной, потому что рисунок не объясняет связь между N и I. Они должны рассматриваться как отдельные переменные.

И также мы не можем исключить член logNI 2 , поскольку переменная N будет доминировать над переменной I в некоторых регионах N x I пробел.

Если рассматривать N как константу, то класс сложности уменьшается до O (I 4 ).

Мы получаем то же самое, если мы рассматриваем N как то же самое, что и I; то есть в вопросе есть опечатка.

(я думаю, что в том, как был задан / сформулирован вопрос, есть ошибка. Если нет, то это вопрос с подвохом , предназначенный для посмотрите, действительно ли вы поняли математические принципы, лежащие в основе сложности, включающей несколько независимых переменных.)

...