- = und ++ = Komplexität auf Scala ArrayBuffer

Question

Ich möchte gut verstehen Komplexität assoziieren mit diesen beiden Funktionen, um eine ordnungsgemäße Komplexität Vergleich zu erreichen.

Mein Problem ist, dass ich ein Array aus einem anderen der Größe n erstellen möchte. Wenn der erste immer kleiner wird, bis er leer ist, wird der andere größer und größer, bis die n Größe wie folgt ist.

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

Ich weiß, dass die Komplexität von der Anzahl der Iterationen hängt das können wir k Iterationen im Durchschnitt sagen, es dauert.

Meine zweite Frage ist, was wird die Komplexität, wenn ich mein erstes Array in b Eimer geschnitten. Nehmen wir an, dass wir einen ArrayBuffer der Größe n haben und wir ihn in zwei Teile der Größe n/2 schneiden, auf die wir die gleichen Schritte wie oben anwenden und wissen, dass die Anzahl der benötigten Iterationen im Allgemeinen weniger wichtig ist als bei uns habe ein Array.

Ich hoffe, dass ich klar genug war. Vielen Dank für Ihre Hilfe.

Answer 1

Da die Array-Größe n ist und ein Element bei jedem Schritt von einem Array zum nächsten verschoben wird, dauert es n Iterationen. Also ist die Komplexität O (n). Wenn Sie in mehrere Buckets aufteilen, ist das Problem immer noch das gleiche. Sie benötigen noch n Operationen, um Daten in das zweite Array zu schreiben. Ihre Quelle hat sich geändert, aber die Anzahl der Vorgänge hat sich nicht geändert.