Gegeben sei ein unsortiertes Array A, überprüfe, ob A [i] = i effizient existiert

Gegeben Array A, überprüfe, ob A [i] = i für irgendein i existiert.Gegeben sei ein unsortiertes Array A, überprüfe, ob A [i] = i effizient existiert

Ich soll das schneller als lineare Zeit lösen, was mir unmöglich erscheint. Die Lösung, die ich mir ausgedacht habe, besteht darin, zuerst das Array in n * log (n) -Zeit zu sortieren, und dann kann man einfach schneller als lineare Zeit überprüfen. Da das Array unsortiert ist, kann ich keine "effiziente" Lösung sehen.

Quelle

2016-12-17 ALEXANDER WORMBS

Auch wenn Sie sortieren, ist es teurer als lineare Zeit. –

Sie haben Recht, das kann nicht schneller als in linearer Zeit auf einem ungeordneten Array getan werden. – dasblinkenlight

Wenn A sortiert ist, ist eine binäre Suche schneller als lineare Zeit. Wenn Sie keine Informationen über A haben, ist dies nicht möglich, da jedes Element übereinstimmen könnte. –

Sie kann nicht einen richtigen Algorithmus mit besser als O(N) Komplexität für ein beliebiges (unsortiertes) Array haben.

Angenommen, Sie haben die Lösung besser als O(N). Es bedeutet, dass der Algorithmus einige Elemente des Arrays auslassen muss, da das Scannen aller Elemente O(N) ist.

Konstruieren Sie A so, dass A[i] != i für alle i dann den Algorithmus ausführen. Lassen Sie A[k] das Element sein, das weggelassen wurde. Weisen Sie k bis A[k], den Algorithmus erneut ausführen - es wird no such items zurückgegeben, wenn k erwartet wird.

Quelle

2016-12-17 12:52:27

Ja, das habe ich erwartet! Danke, dass du es mir bewiesen hast :). Mein Professor muss einen Fehler gemacht haben. –

Nicht wahr. Es gibt keinen solchen Algorithmus, wenn Sie auf eine konstante Anzahl von Prozessoren beschränkt sind. Das ist der einzige Fall, in dem der Beweis gültig ist. Wenn Sie sqrtN-Prozessoren haben, werde ich Ihnen einen O (sqrt N) -Algorithmus geben. @ALEXANDERWORMBS –

@BastianJ: Dein Argument macht überhaupt keinen Sinn. In welchem Universum haben Sie Zugriff auf eine unbegrenzte Anzahl von Prozessoren? Sie könnten auch behaupten, dass jeder Algorithmus O (1) ist. –

Sie erhalten O (log n) mit einem parallelen Algorithmus (Sie haben das nicht eingeschränkt). Starten Sie einfach N Prozessoren in ld (N) Schritten und lassen Sie die Array-Elemente parallel prüfen.

Quelle

2016-12-17 13:17:59

Sicher! Und Sie können das Rucksackproblem in O (1) mit 2 ** n Prozessoren lösen, also muss es O (1) sein, oder? Und verwenden Sie schnellere Prozessoren, wird es O (0,5) werden! –

@EricDuminil Entschuldigung, dass du unverblümt bist, aber du scheinst nicht zu wissen, wovon du sprichst. Ich gab einen parallelen Algorithmus mit O (log n) Zeitkomplexität. Ich bin ziemlich zuversichtlich, dass dies genau die Antwort ist, auf die der Professor des OP gebeten hat. Ihre Behauptung, dass jemand das Rucksackproblem mit der Komplexität von O (1) lösen könnte, ist einfach falsch. Versuche es zu beweisen. Keine Chance. Und Ihr Versuch, sich über mich lustig zu machen, indem Sie O-Notation missbrauchen, ist sowohl albern als auch beleidigend. Ich habe meine Doktorarbeit gemacht. Beweise meine Aussage falsch, dass es einen parallelen Algorithmus mit O (log n) Zeitkomplexität gibt oder sei leise. –

Randnotiz: Ich behaupte, dass es grundsätzlich für jede Funktion f in o (n) einen Algorithmus gibt, der f Prozessoren und O (n/f (n)) Zeit verwendet. Dies schließt den Fall von sqrt (N) Prozessoren und O (sqrt (N)) Zeit ein. –

Gegeben sei ein unsortiertes Array A, überprüfe, ob A [i] = i effizient existiert

Antwort

Verwandte Themen