Ist es möglich, dies zu lösen, mit einer Lösung, deren zeitliche Komplexität besser als linear ist?

Question

Ist es möglich, dieses Problem mit einer Lösung zu lösen, deren zeitliche Komplexität besser als linear ist?

N Glühbirnen sind mit einem Kabel verbunden. Jeder Glühbirne ist ein Schalter zugeordnet, jedoch ändert ein Schalter aufgrund fehlerhafter Verdrahtung auch den Zustand aller Glühbirnen rechts von der aktuellen Glühbirne. Stellen Sie bei einem Anfangszustand aller Lampen die Mindestanzahl an Schaltern fest, die Sie drücken müssen, um alle Lampen einzuschalten. Sie können den gleichen Schalter mehrmals drücken.

Hinweis: 0 bedeutet, dass die Glühbirne ausgeschaltet ist und 1 bedeutet, dass die Glühbirne eingeschaltet ist.

---

Input: [0 1 0 1]

Schritte:

press switch 0 : [1 0 1 0] 
press switch 1 : [1 1 0 1] 
press switch 2 : [1 1 1 0] 
press switch 3 : [1 1 1 1] 

Rückkehr: 4

Answer 1

Das nennt man eine "Lights Out" Rätsel: http://mathworld.wolfram.com/LightsOutPuzzle.html

Eine Geschwindigkeitsverbesserung, die ich mir vorstellen könnte, wäre, die Se zu paralellisieren alle Glühbirnen nach rechts. Insbesondere eine GPU könnte dies effektiv tun (ich bin nicht sicher, da Sie ändern müssen, welche Elemente mit jeder Schleife ausgeführt werden).

Vielleicht macht es eine richtige boolesche Array und bitweise XOR-ing ein Muster auf dem Array?

Wenn der reale Prozess nicht viel komplexer ist als XOR-Boolesche Werte, ist die Speichergeschwindigkeit hier der Engpass - nicht CPU-Zeit. Sofern es sich nicht um rein akademische Zwecke handelt, gilt die Leistungsbewertung sinngemäß: http://ericlippert.com/2012/12/17/performance-rant/