Big O N^2 (Anmeldenummer)

Ich bin ein kompletter Neuling bei Big O und bin ein bisschen ratlos. ich habe:Big O N^2 (Anmeldenummer)

for (int i = 1; i < n*n; i *= 2)

In meinem Kopf gleichsetzen würde dies zu

Bin ich richtig oder kann es zu N vereinfacht werden, wie Sie die Eingänge mit n*n verdoppeln und es mit i *= 2 Halbieren? wenn n * n > (1 << 30)

Quelle

2015-08-23 Matt

In diesem Fall haben Sie

O(log2(n^2))

die

O(2 * log2(n))

oder nur

O(ln N)

Anmerkung ist, dass Sie eine Endlosschleife wird.

Quelle

2015-08-23 14:12:45

Danke @Peter. Ich lag also falsch, danke für die Hilfe. Das wäre also gleich O (2Log2 (n)). Aber wie funktioniert das? Ich dachte, wenn Sie den Eingabebereich verdoppeln, wird es N^2 und wenn Sie die Anzahl der Iterationen halbieren, wird es Log2N, also multiplizieren sie nicht zusammen? Ich habe versucht, jedes Beispiel zu finden, das ich kann und die Muster zu finden, aber das ist ein neues für mich – Matt

@Matt Das Bit-O berücksichtigt nicht den beteiligten Faktor. Dies bedeutet, dass doppelt oder halb O (n) O (n) ist. Deshalb ist O (logBase10 (N)) dasselbe wie O (In N); –

Alles in Ordnung. Macht Sinn. Danke für all deine Hilfe @Peter. – Matt

Antwort

Verwandte Themen