java - Iterator を使用した Vector の BigO

Question

いろいろ調べましたが、いい記事が見つかりませんでした。複数を1つ
に追加し、その後印刷しています：VectorsVector

Iterator it =vector.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }

この関数の Big-O 表記はどのように決定すればよいですか?
たとえば、出力が次の場合:

[何か、何か、何か、何か]
[何か、何か、何か、何か、何か]
[何か、何か、何か、何か、何か、何か] [何か、何か、何か、何か、何か、何か、何か] [何か、何か、何か、何か、何か、何か] [
何か、何か、何か、何か、何か、何か]
、何か、何か、何か、何か、何か、何か、何か]

そして、私が理解していないのは、各行がベクトルであるということです.メインベクトルにはループが必要ですが、その中のベクトルにはループは必要ありません.なぜですか?

score 2 · Accepted Answer

toStringコレクション ( a など)を呼び出すと、そのコレクション内のすべての要素Vectorのカンマ区切りのリストが角かっこで囲まれて取得されます。toString

したがって、コードが行っていることは、すべての要素を順番に呼び出すmain のtoStringeveryを呼び出すことです。したがって、効率は O(n) です。ここで、n は呼び出されるオブジェクトの総数です。VectorVectortoStringtoString

score 1 · Accepted Answer

常にこの「はしごパターン」に従うと仮定します。

最初のベクトルのサイズが 1 で、最後のベクトルのサイズが K の場合、加算式を使用すると、複雑度は次のようになります。

K*(K+1)/2

ここで、最初のベクトルのサイズが k < K の場合、次のようになります。

K(K+1)/2 - (k-1)(k)/2

最後に、「はしごパターン」がなくてもサイズが K 未満の N 個のベクトルがある場合、複雑さは次のようになります。

K*N

それが役に立てば幸い。

2 に答える 2