java - 文字列のすべての部分文字列を見つける複雑さ

Question

これは、文字列のすべての部分文字列を見つけるためのソリューションです。

for (int i = 0; i < str.length(); i++) {
    String subStr;
    for (int j = i; j < str.length(); j++) {
        subStr = str + str.charAt(j));
        System.out.println(subStr);
    }
}

インターネット全体で、このコードの複雑さは O(n ² ) であると読みました。ただし、+ 操作は O(n) 操作です。したがって、私の意見では、複雑さは O(n ³ ) である必要があります。

私が間違っている場合は、私の理解を修正してください。

Answer 1

文字列への文字の追加は O(1) 操作です。で出力を印刷するのに必要な時間も考慮に入れると、O(n ³println ) が得られます。

Answer 2

文字列のすべての部分文字列を見つけるのは O(n ² ) です (部分文字列を見つけるとは、開始インデックスと終了インデックスを決定することを意味します)。部分文字列の総数は O(n ² ) であるため、簡単に確認できます。

しかし、それらをすべて出力するのは O(n ³ ) です。これは、出力する文字の総数が O(n ³ ) であるためです。コードでは、 printlnO(n) の複雑さが追加+されます (適切に使用/実装されている場合、オペレーターは O(1) の複雑さを持つ必要があります)。