Ich habe eine Matrix, die so aussieht:

| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 |

Ich sollte herausfinden, ob diese Matrix eine Spalte hat, die mit allen 1 gefüllt ist. In dieser Matrix ist es Spalte 4. Und es heißt, dass die Zeitkomplexität O (n) und das Gedächtnis O (1) ist.

Diese Matrix repräsentiert eine binäre Beziehung auf einer Menge (von Personen).n ist die Größe der Menge, also ist die Größe der Matrixn * n.

Ich sehe 2 mögliche Lösungen:

Nehmen Sie die erste Spalte, gehen Sie sie durch, wenn Sie Null sehen, springen Sie zur nächsten Spalte und so weiter. Der schlechteste Fall dieses Algorithmus ist jedoch O (n2);Das nächste, wenn ich eine Summe aller Spalten haben werde, dann kann ich eine Antwort in O (n) geben. Unter Aufgabebedingungen wird jedoch nicht gesagt, dass wir Summen berechnet haben. Und wenn ich sie berechne, ist die Komplexität auch O (n2);

Irgendwelche anderen Lösungen?