Lösungen, die Schleife über zwei Eingabe-Arrays beinhalten: O (n + m) oder O (n * m)

Ich wurde eine Frage gestellt, in der wir nach doppelten Sozialversicherungsnummern suchen, wie in ssn, die in beiden Array sind A und auch Array B. Mein unmittelbarer Gedanke war, über jedes Array zu iterieren, das die Anzahl jedes ssn in einer HashMap speichert. Dann sind natürlich alle Schlüssel, die mehr als 1 zählen, Duplikate. Mein Verständnis war, dass dies eine O (n + m) -Operation wäre, wobei m und n die Anzahl der Elemente in jedem Array sind. Mir wurde gesagt, dass dies in Bezug auf die Zeitkomplexität "sehr ineffizient" ist und dass die Zeitkomplexität tatsächlich O (n * m) ist. Wie ist das korrekt?Lösungen, die Schleife über zwei Eingabe-Arrays beinhalten: O (n + m) oder O (n * m)

Quelle

2017-02-05 Elroy Jetson

Ja, das ist definitiv O (n + m). –

"Mir wurde gesagt ..." Von wem erzählt? Warum spielt es eine Rolle? Es klingt ziemlich seltsam. Es ist im Durchschnitt linear. Im schlimmsten Fall ist es quadratisch. – kraskevich

@JoeC das war was ich dachte. Wie korrigieren Sie einen Interviewer, ohne wie ein vollständiges Werkzeug zu klingen? –

Zunächst ist O(n+m) schneller als O(n*m). Zeitkomplexität von O(n*m) wird der Fall sein, wenn Sie zwei Schleifen wie dieses:

for x in [1..n] 
    for y in [1..m]

So bedeutet der Begriff „sehr ineffizient“ überhaupt nicht gelten, es sei denn, es ist ein Knirschen von zusätzlichen Platz dass O(n+m) entsteht. In diesem Fall können Sie klären, was der wichtigste Faktor ist Zeitkomplexität oder Raumkomplexität.

Quelle

2017-02-06 04:41:16

Lösungen, die Schleife über zwei Eingabe-Arrays beinhalten: O (n + m) oder O (n * m)

Antwort

Verwandte Themen