Ich bin mit zwei Zeitkomplexitäten festgefahren. Um eine binäre Suche mit sortierten Array durchzuführen, ist O (logN). Um ein unsortiertes Array zu durchsuchen, müssen wir es zuerst sortieren, so dass es zu O (NlogN) wird. Also können wir eine binäre Suche durchführen, die die Komplexität als O (N) ergibt, aber ich habe gelesen, dass es O (NlogN) sein könnte. Welches ist richtig?Zeit Komplexität der binären Suche nach einem unsortierten Array
Binäre Suche ist für "sortierte" Listen. Die Komplexität ist O (logn).
Binäre Suche funktioniert nicht für "unsortierte" Listen. Führen Sie für diese Listen nur eine gerade Suche durch, beginnend mit dem ersten Element; Dies ergibt eine Komplexität von O (n). Wenn Sie das Array mit MergeSort oder einem anderen O (nlogn) -Algorithmus sortieren würden, wäre die Komplexität O (nlogn).
O (log n) < O (n) < O (n log n)
BinarySearch funktioniert auch dann, wenn das Array ein wenig unsortiert ist. Gut zu beachten. – ofarooq
Die Antwort auf Ihre Frage in Ihrer Frage selbst ist. Sie sortieren zuerst die Liste. Wenn Sie Ihre Liste mit Schnell- oder Mischsortierung sortieren, wird die Komplexität zu o (n log n). Teil - 1 kommt über. Der zweite Teil der Durchführung einer binären Suche wird in der 'Sortierten Liste' durchgeführt. Die Komplexität der binären Suche ist o (log n). Daher bleibt letztlich die Komplexität des Programms o (n log n). Wenn Sie jedoch den Median des Arrays berechnen möchten, müssen Sie die Liste nicht sortieren. Eine einfache Anwendung einer linearen oder sequenziellen Suche kann Ihnen dabei helfen.
Die Zeitkomplexität der linearen Suche ist O(n) und die der binären Suche ist O(log n) (log base-2). Wenn wir ein unsortiertes Array haben und die Binärsuche dafür verwenden wollen, müssen wir zuerst das Array sortieren. Und hier müssen wir eine Zeit O(n logn) verbringen, um das Array zu sortieren und dann Zeit zu verbringen, um Element zu suchen.
Das sind zwei getrennte Operationen. Die binäre Suche wird immer ** O (log n) ** unabhängig sein. – squiguy
Es stimmt, eine binäre Suche funktioniert nicht in einem unsortierten Array. Sie müssen jedoch zuerst das Array sortieren, um die binäre Suche durchzuführen. Zumindest habe ich das in letzter Zeit gelernt. – user2373448