Big o vs Big $ \ theta $ Während des Codierinterviews

Question

fast jedes Mal, wenn ich einen Artikel über den Zeit- oder Raumkomplexität sehe, drückt die Menschen die Komplexität mit großem O aus, während es $ \ theta $ sein sollte. Aus dem Buch "Cracking the codierende Interview":

"In der Industrie (und deshalb in Interviews) scheinen die Menschen zusammen miteinander verbunden zu sein und

Answer 1

Hier ist eine Antwort von Reddit, die ich am nützlichsten fand:

Ich denke, ich würde sagen, wenn jemand sagt: "Was ist ein Insertionsort?", Willst du sagen: "Es ist $ o (n ^ 2) $ ".Sicher ist es nicht genau dasselbe wie gesagt, dass es " $ \ theta (n ^ 2) $ im schlimmsten Fall" ist, aber es ist eine Konvention, die jeder versteht, undEs dauert weniger Zeit, um die Worte aus dem Mund zu bekommen.

Answer 2

Ich denke, es ist gut.Es zeigt nur den Interviewer, den Sie tatsächlich wissen, was die eigentliche Bedeutung von Big-O und Theta sind.Stellen Sie einfach sicher, dass es tatsächlich trifft (der $ \ omega $ teil), wenn Sie über einen komplizierten Algorithmus verfügen, und Sie haben einige Ungleichheit für Big-O-Komplexitätsnachweis verwendet.

.

Answer 3

Wenn Sie Big-Theta erwähnt, werden viele Interviewer denken, dass Sie falsch sind, weil sie nie davon gehört haben.Wenn Sie dann anfangen, es zu debieren, scheitern Sie, worauf das Interview in erster Linie ist: Überzeugung des Interviews, den sie mit Ihnen zusammenarbeiten möchten.

Frage: Sie prüfen, ob X ein Primzahl ist, indem Sie die Teilbarkeit der Teilbarkeit um 2, 3, 5, 7, 11 usw. testen. Was ist das Big-o der Zeitkomplexität?Wenn Sie antworten, "es ist Big-Theta", was wird meine Meinung von Ihnen sein?