Временная сложность тройной вложенной петли с квадратными индексами

Question

Я видел эту функцию в экзаменационном документе прошлого года.

public static void run(int n){
    for(int i = 1 ; i * i < n ; i++){
        for(int j = i ; j * j < n ; j++){
            for(int k = j ; k * k < n ; k++){

            }
        }
    }
}

После некоторого примера, я думаю, это функция, которая со сложностью времени в следующей формуле

Дайте сделать m = n^(1/2)

M+(M-1)+(M-2)+...+3+2+1]+[(M-1)+(M-2)+...+3+2+1]+. ..... + (3 + 2 + 1) + (2 + 1) + 1

*РЕДАКТИРОВАТЬ: Я задал этот математический вопрос здесь, ответ m (M+1) (M+2)/6

Правильно ли это, если нет, что не так, если да, как бы вы перевели в Big O записи. Вопрос, который я хочу задать, не Только об этом конкретном примере; Но также, как бы вы оценили алгоритм, скажем, я могу привести только какой -то пример, чтобы посмотреть, как он появляется. Но некоторые алгоритм не так просты в оценке, как вы оцените, используя этот пример.

РЕДАКТИРОВАТЬ: @luchiangrigore @aleksg

public static void run(int n){
        for(int i = 1 ; i * i < n ; i++){
            for(int j = 1 ; j * j < n ; j++){
                for(int k = 1 ; k * k < n ; k++){

                }
            }
        }
    }

Это пример того, что в записи моей лекции каждый цикл с сложностью времени не к силе 1/2, для каждого цикла есть еще один n^(1/2) внутри, общая сумма N^(1/2) * n^(1/2) * n^(1/2) = N^(3/2) Анкет Первый пример такой же? Это меньше, чем второй пример, верно?

Редактировать, добавить:

Как насчет этого? Это log (n)*n^(1/2)*log (n^2)

for (int i = 1; i < n; i *= 2)
            for (int j = i; j * j < n; j++)
                for (int m = j; j < n * n; j *= 2)

Answer 1

Для одной из петлей вы сложность $ O ( sqrt n) $. Вы гнездовываете петли три раза, так что вы получите сложность $ O ( sqrt n^3) $, которая составляет $ O (n^{3/2}) $.

Если вы хотите быть более точным, то для вашего первоначального вопроса сложность будет:

1. $ O ( sqrt n) $ для первого цикла
2. $ O ( sqrt n - 1) $ для второго цикла, который такой же, как $ o ( sqrt n) $, так как время сложности времени 1 постоянно.
3. $ O ( sqrt n - 2) $ для третьего цикла, который такой же, как $ o ( sqrt n) $, так как время сложности времени 2 постоянно.

Следовательно, общая сложность по -прежнему остается $ o ( sqrt n^3) = O (n^{3/2}) $.

Редактировать/добавить:

Вы в значительной степени правы, просто сделайте еще один шаг, чтобы упростить выражение, помня, что $ log (n^2) = 2 times log (n) $. Есть три петли:

1. Первый на, правильно, $ o ( log n) $.
2. Второй такой же, как в первой проблеме, так что вы получаете $ o ( sqrt n) $.
3. Третий находится на квадрате $ n $, поэтому вы получаете $ o ( log (n^2)) $, что такое же, как $ o (2 log (n)) $, что такое же, как $ O ( log (n)) $.

Сочетание трех, это в значительной степени похоже на умножение, вы получите: $ o ( log (n) times sqrt n times log (n)) $, который $ o ( log (n)^2 times sqrt n) $.