Musteraufgabe

Ein erster Ansatz

Das Programm probiert von jeder Startposition aus jede Länge durch und merkt sich das Maximum.

#include <cstdio>

using namespace std;

float values [1000000];
int N;

int main ()
{
  FILE *fin = fopen ("aktie.in", "r"),
       *fout = fopen ("aktie.out", "w");

  fscanf (fin, "%d", &N);
  for (int n = 0; n < N; n++)
    fscanf (fin, "%f", &values [n]);

  int maxStart = 1, maxLen = 0;
  float maxValue = 0;
  for (int start = 0; start < N; start++) { // für jede Startposition
    for (int len = 1; start + len <= N; len++) { // für jede Länge
      float summe = 0;
      for (int pos = start; pos < start + len; pos++) {// aufsummieren
        summe += values [pos];
      }
      if (summe > maxValue) {
        maxValue = summe;
        maxStart = start;
        maxLen = len;
      }
    }
  }

  fprintf (fout, "%d\n%d\n", maxStart, maxLen);

  fclose (fin); fclose (fout);
  return 0;
}

Die "Zeitkomplexität"

Wenn man sich den Programmablauf überlegt, stellt man schnell fest, dass die Zeile summe += values [pos]; am häufigsten aufgerufen wird. Um herauszufinden, wie gut oder schlecht das Programm hinsichtlich seiner Laufzeit ist, kann man versuchen zu berechnen, wie häufig diese Zeile ausgeführt werden muss, bevor das Programm beendet wird. Betrachten wir zunächst die Beispieleingabe mit N=10. Die ganz äußere Schleife

for (int start = 0; start < N; start++) {
  ...
}

wird genau 10 mal, also N Mal, ausgeführt.

Etwas komplizierter sieht es mit der zweiten Schleife aus: die Anzahl ihrer Durchläufe ist abhängig vom Wert "start" aus der äußeren Schleife. Zunächst hat diese Schleife 10 Durchläufe, wenn sie das nächste Mal ausgeführt wird noch 9, dann 8 usw. Insgesamt wird der Code in der Schleife für die Beispieleingabe also 10+9+8+...+2+1 = 55 Mal ausgeführt. Allgemein kann man sagen, dass der Code N+ (N-1)+ (N-2)+...+2+1 Mal ausgeführt wird. Der Wert dieser Summe lässt sich mit der Formel (N+1) * N / 2 berechnen.

Noch komplizierter wird es dann mit der ganz inneren Schleife, also der Anweisung, an der wir eigentlich interessiert sind. Sie wird immer genau "len" mal ausgeführt. Für unser Beispiel bedeutet das (10+9+...+2+1) + (9+8+...+2+1) + ... + (1) = 10 * 11 / 2 + 9 * 10 / 2 +...+ 1 * 2 / 2 = 220 Mal. Die allgemeine Formel für diese Zahl lautet übrigens N * (N+1) * (N + 2) / 6. Das Erfreuliche ist allerdings, dass es eigentlich unnötig ist, die Formel so genau zu kennen. Es reicht völlig aus, das ungefähre Verhalten für große N zu kennen. Man kann beispielsweise vereinfachend sagen, dass alle Schleifen auf jedenfall "N mal oder weniger" ausgeführt werden. Damit würde dann die innerste Anweisung N^ 3 Mal ausgeführt. Da die genaue Formel auch ein Polynom dritten Grades ist, wird sie sich vom Verlauf her mit steigendem N auch ähnlich verhalten und praktisch nur um einen etwa konstanten Faktor abweichen:

N	Abschätzung	Genaue Formel	Faktor
10	1000	220	4.55
100	1000000	171700	5.82
390	59319000	9962680	5.95
1000	1000000000	167167000	5.98
5000	125000000000	20845835000	6.00

Wie man leicht beobachten kann, nähert sich dieser Faktor mit steigendem N scheinbar beliebig nahe an 6 an. Um die Anzahl der Ausführungen der innersten Anweisung jetzt in eine konkrete Laufzeit in Sekunden umzurechnen, muss man diese Anzahl noch mit einem konstanten Zeitfaktor multiplizieren. Moderne Rechner sollten im Moment etwa 10000000 solcher Anweisungen (summe += values [pos];) in einer Sekunde ausführen können. Das wiederum bedeutet, dass das obige Programm mit bis zu etwa 390 Kursänderungen klarkommt, wenn es nur eine Sekunde laufen darf. Es ist also zu langsam, um mit bis zu 1000000 Werten umzugehen. Auch der konstante Faktor 6 ändert an dieser Tatsache nichts, denn selbst wenn der Rechner 60000000 Anweisungen pro Sekunde verarbeiten könnte, würde das Programm nur mit bis zu 710 Werten zurecht kommen. Zulässige Werte steigen also längst nicht so schnell wie die Anzahl der Anweisungen, die pro Sekunde ausgeführt werden.

Da die Programmschritte mit der Funktion N^3 abgeschätzt werden können, sagt man, dass Programm hat "kubische Laufzeit". Man schreibt dafür O(N^3) [sprich "O von N hoch drei", Big-O-Notation genannt]. Dies bedeutet, dass wir eine obere Grenze für die Laufzeit unseres Programms in Programmschritten angeben können, nämlich a * N^3. Die Laufzeit ist nicht von den konkreten Eingabewerten, abgesehen von N, abhängig.

Speicherkomplexität

Die gleiche Analyse wie mit der Laufzeit lässt sich natürlich auch mit der Arbeitsspeicherverwendung durchführen, denn auch der Arbeitsspeicher ist meist mit 16 oder 32 Megabytes begrenzt. Im Beispielprogramm wird mit dem Feld "values" mit Abstand am meisten Speicher belegt. Da N begrenzt ist, kann die Größe statisch auf das Maximum festgelegt werden. Eigentlich ist die Größe aber von N abhängig, nämlich linear. Von der Speicherkomplexität her ist das Programm also ausreichend effizient, denn 1000000 floats entsprechen bei 4 Bytes pro float etwa 4 Megabytes.