2 Arrays vergleichen - #81786 (Allgemeines zu Perl)

esskar

2004-04-23 02:36

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

Die Landau-symbole (O, o, Theta, ...) unterliegen folgender Motivation:

- Suchen kompakte Notation zur Aufwandsabschatzung von Algorithmen.
- Algorithmus soll von Problemgrößen abhängen (z.B.: n = Zahl der zu sortierenden Objekte in einer Liste)

Code: (dl )

foreach my $i (@array)
{
   $sum += $i;
}

Läuft in genau n Schritten ab; wobei n = scalar @array ist; und überschreitet nie die Zahl n; also O(n)

Okay... wenn also was in O(n) läuft, läuft es linear;
O(1) heißt konstant; O(log n) heißt dann logarithmisch und O(n^2) heißt quadratisch

Code: (dl )

foreach my $j (@brray)
{
   foreach my $i (@array)
   {
      $sum += $i;
      $sum *= $j;
  }
}

Sei n = scalar @array und m = scalar @brray, dann ist die Laufzeit O(m * n), weil du m mal das @array durchläufst
wenn m == n gilt, dann ist die Laufzeit O(n^2) und wenn
m = n^2 ist, dann wäre die Laufzeit O(n^3)...

Da Plus, Minus, Mal, Geteilt Funktionen sind, die so schnell ausgeführt werden können, dass man deren Laufzeitverhalten unter den Tisch fallen lässt (Sind Funktionen, die in Konstanter Zeit ausgeführt werden können, also O(1) und n*1 = n), wäre man jetzt eigentlich fertig.

Aber wie sieht es hiermit aus?

Code: (dl )

foreach my $i (@array)
{
   calc($i);
}

Eigentlich hat dies auch die Laufzeit O(n), aber nur unabhängig von der Funktion calc...

calc könnte so aussehen

Code: (dl )

sub calc
{
   my ($var) = @_;
   my $text = $var x 10000; 
   print md5($text);
}

Okay, print vernachlässigen wir wieder, obwohl eine Ausgabe schon zeit kosten kann, aber md5 ist nicht gerade flink.

Also, kann man hier nicht mehr von O(n) sprechen, da man die Laufzeit von md5 auf einen String der länge length($var) * 10000 berücksichtigen muss. Verstanden?

Um nochmal zum Hash zurück zukommen.
Für den Benutzer wirkt die Laufzeit von $hash{$key} Konstant; also O(1)...

In Perl selber muss aber noch eine Operation ausgeführt werden, damit der Wert, der dem Schlüssel zugeordnet ist, gefunden werden kann.