Understanding Big Oh Karrierecracking Coding Interview

Question

Es gibt eine Beispielfrage in dem Buch Careercup Cracking Coding Interview (CCIS).

drucken alle positiven ganzzahligen Lösungen der Gleichung a + b 3 = c 3 + d und d ganze Zahlen zwischen 1 und 1000.

Sie gaben drei Lösungen Zwei davon werde ich hier zeigen.

Beispiel 1

1 n = 1000 2 for a from 1 to n 3 for b from 1 to n 4 for c from 1 to n S for d from 1 to n 6 if a^3 + b^3 == c^3 + d^3 7 print a, b, c, d

Beispiel 2

1 n = 1000 2 for a from 1 to n 3 for b from 1 to n 4 for c from 1 to n 5 d = pow(a3 + b3 - c3 , 1/3) // Will round to int 6 if a^3 + b^3 == c^3 + d^3// Validate that the value works 7 print a, b, c, d

Das Buch heißt es, dass die erste Frage, O (n) ist und das zweite ist O (n). Meine Frage ist, warum ignorieren sie die Komplexität von pow

Answer 1

Big O drückt aus, wie die Funktion mit n wächst. Die pow-Funktion, insbesondere wenn das zweite Argument 1/3 ist, wächst nicht mit n. Das heißt, pow ist O (1). Sie können sich O (1) als Identitätsfunktion vorstellen. O (n) + O (1) = O (n) genau wie 2 + 0 = 2.

Answer 2

Sie können sagen, dass sie es nicht ignorieren, aber angenommen, dass die Komplexität O(1) ist. Die Ausrichtung kann wie folgt aussehen:

Sie müssen eine Funktion erstellen, die eine Kubikwurzel (ganzzahliger Wert) einer Zahl von 0 bis 1000^3 berechnet. Wie würdest du es umsetzen? Ein einfacher Weg ist eine binäre Suche (es gibt bessere Möglichkeiten, wie numerische Methoden). Wie viele Iterationen werden Sie brauchen: log2(1000^3) was ungefähr 30 ist. So Art von O(1).