- = and ++ = Scala ArrayBufferの複雑さ

Question

適切な複雑さの比較を達成するために、この2つの関数に関連する複雑さをよく理解したいと思います。

私の問題は、別のサイズのnから配列を作成したいということです。最初のものが空になるまで小さくなると、次のようにnサイズになるまでもう一方は大きくなります。

while(ArrayBuffer2.size != n) { 
    ArrayBufferX = ArrayBuffer1.filter(...) 
    ArrayBuffer1 --= ArrayBufferX 
    ArrayBuffer2 ++= ArrayBufferX 
} 

私は複雑さが反復回数に依存することを知っています。平均してk回の反復が必要です。

私の2番目の質問は、私が最初の配列をバケットにカットするときの複雑さです。

私たちは、サイズがnのArrayBufferを持っていて、2つのサイズのn/2でそれをカットしたとしましょう。上記の手順と同じステップを適用します。一般的に、リコートされた反復回数は、 1つの配列があります。

私は十分に明確であることを望みます。 ありがとうございます。

Answer 1

アレイサイズがnで、各ステップで1つのアレイから別のアレイに1つのアイテムを移動すると、n回の反復が必要です。したがって、複雑さはO（n）です。複数のバケットに分解しても、問題は同じです。 2番目の配列にデータを格納するには、n個の操作が必要です。ソースは変更されていますが、操作の数は変更されていません。