二乗インデックスを備えたトリプルネストループの時間の複雑さ

Question

私はこの機能を過去1年間の試験論文で見ました。

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

これは正しいですか、いいえ、何が間違っているのか、はいの場合、どのように大きな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++){

                }
            }
        }
    }

これは、私の講義ノートでは、各ループが時間の複雑さを伴う例です。 n の力に 1/2, 、ループごとに別のn^（1/2）があり、合計はn^（1/2） * n^（1/2） * n^（1/2）= n^（3/2）です。最初の例は同じですか？ 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

ループの1つでは、$ o（ sqrt n）$の複雑さがあります。ループを3回ネストするので、$ o（ sqrt n^3）$の複雑さが得られます。これは$ o（n^{3/2}）$です。

あなたがもっと正確になりたいなら、あなたの元の質問のために、複雑さは次のとおりです。

1. 最初のループの$ o（ sqrt n）$
2. $ o（ sqrt n -1）$ for 2番目のループの場合、これは$ o（ sqrt n）$と同じです。 1 一定です。
3. $ o（ sqrt n -2）$ for 3番目のループの場合、これは$ o（ sqrt n）$と同じです。 2 一定です。

したがって、合計の複雑さはまだ$ o（ sqrt n^3）= o（n^{3/2}）$です。

編集/追加：

あなたはかなり正しいです。$ log（n^2）= 2 times log（n）$を覚えていることを思い出して、式を単純化するためのもう1つのステップを作成してください。 3つのループがあります：

1. 最初は正しく、$ o（ log n）$です。
2. 2番目の問題は最初の問題とまったく同じので、$ o（ sqrt n）$を取得します。
3. 3番目は$ n $の正方形です。したがって、$ o（ log（n^2））$を取得します。これは$ o（2 log（n））$と同じです。 $ o（ log（n））$。

3つを組み合わせると、それは多重化によく似ています。$ o（ log（n） times sqrt n times log（n））$を取得します。これは$ o（ log（n）^2です times sqrt n）$。