Implementierungsprobleme
Beim Umgang mit Algorithmen und Datenstrukturen haben manche Menschen manchmal den Eindruck, diese seien äußerst kompliziert. In der Regel jedoch sind sie recht einfach und intuitiv. Alles, was man wirklich braucht, um ein Gespür dafür zu entwickeln, wie die Algorithmen tatsächlich arbeiten, ist etwas Übung und praktische Erfahrung.
Wenn man konkrete Aufgaben und Übungen betrachtet, wird schnell deutlich, dass sich manche Aufgabengruppen gut zusammenfassen lassen. Sie weisen gemeinsame Merkmale auf, sodass sich bestimmte Techniken auf die gesamte Gruppe anwenden lassen.
Eine dieser Gruppen bilden die Implementierungsprobleme. Solche Aufgaben enthalten meist schon im Aufgabentext die Schritte, die zur Lösung führen. Das heißt, die erforderlichen Aktionen sind bereits beschrieben, und die Aufgabe der Softwareingenieurin oder des Softwareingenieurs besteht hauptsächlich darin, diese Schritte möglichst effizient umzusetzen, um das gewünschte Ergebnis zu erhalten. Dennoch kann es vorkommen, dass die direkte Umsetzung nicht ganz trivial ist, selbst wenn die Schritte bereits festgelegt sind.
Challenge - Find the missing number
Given all the numbers from 1 to
n except one, you are asked to find the missing number.Input
The first line of the input contains a single integer
n (2 ≤ n ≤ 100 000).The second line of the input contains
n-1 space-separated integers (1 ≤ ≤ n).Output
The program should print the missing number.
Examples
Eingabe | Ausgabe |
4
3 4 1 | 2 |
3
2 1 | 3 |
Tutorial zu Komplexität und Big -Notation
Auch wenn die oben beschriebene Aufgabe einfach erscheint, wird eine naive Lösung nicht schnell genug sein, um alle Testfälle zu bestehen.
Eine naive Herangehensweise könnte sein, alle Elemente aus der Eingabe in eine Liste einzulesen und dann für alle Zahlen von
1...n zu prüfen, ob diese in der Liste enthalten sind. Falls nicht, haben wir die fehlende Zahl gefunden:n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n Operationen
if i not in a: # n Operationen (durchläuft alle Elemente)
print(i) # Wir haben die Lösung gefunden!Dieser Algorithmus ist jedoch sehr langsam. Er läuft alle Zahlen von
1...n durch und prüft jeweils, ob die aktuelle Zahl in der Liste ist. Diese Prüfung ist ein linearer Vorgang: Das Programm durchsucht dabei jedes Element der Liste a, um festzustellen, ob i enthalten ist oder nicht. Daher benötigt das Programm für das Überprüfen von i in a etwa n Operationen (die Liste hat grob n Elemente, genau genommen n-1, aber das ändert kaum etwas).Insgesamt führt dieses Vorgehen also etwa Operationen aus. Die äußere Schleife läuft
n Mal, und das Überprüfen, ob sich ein Element in der Liste befindet, kostet pro Durchlauf nochmals n Operationen. Somit kommt man auf etwa Operationen (im schlimmsten Fall).💻
Unsere Computer können ungefähr 10–100 Millionen Operationen pro Sekunde ausführen. Wenn das Zeitlimit einer Aufgabe bei 1 Sekunde liegt (was bei algorithmischen Problemen häufig vorkommt), sollten wir uns auf maximal 100 Millionen Operationen beschränken.
Bei der oben beschriebenen Aufgabe kann
n bis zu 100 000 betragen. Das bedeutet, dass der Algorithmus Operationen ausführt, was 10 Milliarden entspricht. Auf einem normalen Rechner würde das etwa 100 Sekunden dauern, während das Zeitlimit bei nur einer Sekunde liegt. Wir brauchen also eine effizientere Lösung.Big -Notation
Die Big -Notation ist eine mathematische Schreibweise, um die obere Grenze der Wachstumsrate der Laufzeit eines Algorithmus im Verhältnis zur Eingabedatenmenge zu beschreiben. Sie liefert eine grobe Schätzung, wie viele Operationen ein Algorithmus im Verhältnis zur Größe seiner Eingabe ausführt.
Für dieses Problem haben wir ermittelt, dass der naive Algorithmus insgesamt etwa Operationen benötigt. Wir können die Komplexität daher als angeben.
Später im Kurs werden wir dies noch näher erläutern, um mehr Intuition und formale Grundlagen zu vermitteln.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB