Komplexität von Funktion bestimmen?

Bild zum Beitrag

Das ist die Funktion. Leider gibts für die Aufgabe keine Lösung, aber ich hätte gesagt, dass die innere Schleife log_2(n) Höchstens log_2(n) Durchläufe hat, weil k ja immer mindestens halbiert wird. Zusammen mit der äußeren Schleife wäre das n * log n

Aber die äußere Schleife macht ja eigentlich nichts, wenn k = 0 ist. Muss das n dann trotzdem mitberechnet werden oder würde hier auch ein log n reichen, sodass es auf log^2 n rauslaufen würde?

06.07.2020, 23:29

Als Lösung muss x so gewählt werden (das kleinste x ist gesucht), dass der Algorithmus in O(n^x) ist.

Lässt sich n log n überhaupt so darstellen?

2 Antworten

Nevron

07.07.2020, 08:27

Du weist n der Variable k zu. In dem Fall wäre k == n. Das passiert wo du sagst

int k = n;

Die äußere Schleife wird daher mit n Durchläufen durchlaufen, da du es ja übergibst. Weiter unten weißt du den Wert n k zu.

Die äußere Schleife wird 1 mal durchlaufen und die innere n Mal. Bevor er WIEDER in die äußere Schleife gesprungen wird, wird return aufgerufen und sum zurückgegeben.

Gurkenhaft

07.07.2020, 11:38

Und wo ist das k/2?

Nevron

07.07.2020, 12:44

@Gurkenhaft

Ich denke das war klar dass sich k dann verkleinert.

frage522

06.07.2020, 23:08

die Äussere schleife und die innere werden jeweils n mal durch laufen

algorithmenjaja

Fragesteller

06.07.2020, 23:10

Wieso wird die innere n mal durchlaufen?

frage522

06.07.2020, 23:18

@algorithmenjaja

weil k=n gilt

algorithmenjaja

Fragesteller

06.07.2020, 23:20

@frage522

Aber k wird auch pro Durchlauf der äußeren Schleife halbiert. Ändert das nichts?

frage522

06.07.2020, 23:21

@algorithmenjaja

stimmt, das hab ich über sehen, dann stimmt für innen das log von dir

algorithmenjaja

Fragesteller

06.07.2020, 23:22

@frage522

okay danke :D

Lineare Listen haben erstmal sehr viele Nachteile...

Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)
Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionieren
Sortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat.
Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.

Dagegen sind Bäume:

Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss)
Suche funktioniert aufbaubedingt IMMER in O(log(n))
Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortieren
Die Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).

Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?

...zur Frage

C Programmcode Ceasar Cipher?

Hallo,

die aufgabe ist folgende:

Schreiben Sie eine Funktion, welche eine Variante des [Caesar Cipher](https://en.wikipedia.org/wiki/Caesar_cipher) auf einen String anwendet. Hierbei wird anstatt eines vorgegebenen Betrages und einer vorgegebenen Richtung für die Chiffrierung der Schlüssel für jeden Buchstaben des Klartextes neu berechnet.

Funktionsweise:

Jede Verschiebung erfolgt abhängig vom Schlüssel. Ist der Schlüssel für das aktuelle Zeichen eine gerade Zahl, so wird das aktuelle Zeichen um diesen Betrag im Alphabet nach rechts verschoben (z.B. beim Schlüssel 2 wird aus einem A ein C). Ist der Schlüssel ungerade, so erfolgt eine Verschiebung nach links (z.B. beim Schlüssel 3 wird aus einem D ein A).

Würde eine Verschiebung über das Ende des Alphabets hinaus erfolgen, so wird die Zählung bei Beginn des Alphabets fortgesetzt. Beim Schlüssel 2 wird aus einem Z also ein B bzw. beim Schlüssel 3 aus einem A ein X.

Es werden nur Buchstaben des englsichen Alphabets (A-Z und a-z) chiffriert. Alle anderen Zeichen bleiben unverändert.

Der Startschlüssel wird nur auf das erste Zeichen angewendet. Danach wird der Schlüssel nach jeder Anwendung neu berechnet, indem der Zahlenwert des zuletzt veränderten Klartext-Zeichens (also 1 für A und a, 2 für B und b, bis 26 für Z und z) durch den zuletzt verwendeten Schlüssel dividiert wird. Der neue Schlüssel für das nächste Zeichen ist der ganzzahlige Rest dieser Division. Falls es hierbei zu einer Division durch Null kommen würde (weil der zuletzt verwendete Schlüssel 0 war) wird der neue Schlüssel wieder auf den Wert des Startschlüssels gesetzt.

Folgenden Code habe ich bis jetzt geschrieben, allerdings bekomm ich bei großen Schlüsseln (zb: start_key = 100) falsche Ergebnisse raus. Weiß glaube ich auch warum: Mein Algorithmus funktioniert ja über Werteverschiebung, d.h. ab einem bestimmt großen Wert des Schlüssels verschiebt sich mein Zahlenwert des chars zu weit und dann stimmt meine "Formel" nicht mehr. Hätte es jetzt damit gelöst, dass ich zuerst mit einer if Schleife auf einen zu großen Key prüfe (zB.: if Key > 25), anschließend dividiere ich diesen Key und gehe mit dem Ergebniss in eine neue Schleife rein wobei jetzt anstatt des Keys der neue Wert addiert bzw subtrahiert wird. Anschließend durchlaufe ich diese Schleife Key%25 mal.

Aber wie setze ich das um? Zusätzlich dazu wird der Code dann mega unübersichtlich und viel zu lang für eine simple Funktion. Gibt es auch andere Möglichkeiten als meinen Code?

Ps: Ich sende den Code extra weil sonst das Zeichenlimit überschritten wird

...zur Frage

Funktion F mit der Basis e?

Aufgabe: Schreiben Sie die Funktion f mit der Basis e und bestimmen Sie die ersten beiden Ableitungen von f ?
Bsp: f (x) = 3^x

Ich weiß nicht ganz ich da tun soll. Im Unterricht haben wir uns diese Formel aufgeschrieben: log (a^b) =b*log(a)

Ich habe zwar die Lösungen zu meinen Aufgaben hier gefunden, aber kann nichts mit ihnen anfangen. Kann mir jemand helfen?

...zur Frage

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zur Frage

Hilfe bei Dezimal, Hexal, Oktal und Hexadezimaldarstellung (c Programm?

Hi,

ich muss diese Aufgabe lösen. Ich versteh auf was die Aufgabe hinauswill (Schleifen, etc). Komme jedoch nicht weiter bei der Frage, wie ich in Hexadezimal, oktal usw Zahlen darstelle. Ich brauche nicht die Lösung der Aufgabe nur Hilfe bei der Darstellung der Zahlen. Danke schonmal :)

Gruß

...zur Frage

Wie lasse ich Anzahl der Durchläufe einer C++ Do-while Schleife ausgeben?

Guten Abend!

Ich hoffe mir kann jemand helfen, es geht um das Programmieren in C++.

Ich muss ein Programm schreiben in dem eine do-while Schleife vorkommt. In der Schleife selbst stehen nur Funktionen, die ich vor der Schleife definiert habe. Das passt alles...

Nun soll ich aber am Ende neben dem Ergebnis noch ausgeben, wie oft die Schleife durchgelaufen ist.. Leider habe ich keine Ahnung und auch keine Idee wie ich das machen kann.

Könnte mir da jemand helfen, wenn möglich freue ich mich auch über ein kleines Beispiel.

Grüße und danke im Voraus!

...zur Frage

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zur Frage

Themenbereiche Informatik - Eure Lieblingsthemen?

Es kann sein, dass ich nicht alles angegeben habe, aber dafür gibt es den Bereich "Anderes".

Danke Euch.

...zur Frage

Java Bubble Sort Algorithmus programmieren wer kann mir helfen (bitte keine Lösung schreiben sondern nur Tipps geben)?

Die Aufgabenstellung lautet:

"Damit Sie sehen wie nervig das Sortieren eines Arrays wirklich sein kann wenn man es selbst programmieren muss: implementieren Sie einen einfachen Sortieralgorithmus in einer Methode namens 'bubblesort'. Diese Methode erwartet einen Parameter 'x' wie in der letzten Aufgabe, und verfährt auch genauso mit ihm. Die Sortierung wird wie folgt durchgeführt: angefangen beim zweiten Array-Element (also mit Index 1) prüfen Sie für alle Elemente, ob sie kleiner sind als ihr Vorgänger, und vertauschen sie sofort falls ja. Dies wird so lange durchgeführt, bis bei einem kompletten Durchlauf durch das Array (beginnend bei Index 1) keine Vertauschung mehr vorgenommen werden muss, in diesem Fall ist das Array sortiert. Falls das Array 0 oder 1 Elemente hat muss nichts getan werden da solche Arrays bereits sortiert sind (warum?). Tipp: die perfekte Gelegenheit eine do/while-Schleife zu benutzen!"

Mit freundlichen Grüßen

...zur Frage

Algorithmus herausfinden von Zahlenfolge?

Ich habe eine Zahlenfolge, wie z.B. 5, 10, 18, 32, 52. Die mehr oder weniger eine Kurve darstellen. Hab bei Log,Sin,Cos aber nicht so wirklich aufgepasst...

Wie kann ich den zugrundeliegenden Algorithmus herausfinden?

Edit:

Es geht um Exp/Lvl bei einem Videospiel. Wie das System funktioniert weiß ich leider nicht, aber ich habe ziemlich viele Werte:

5, 10, 18, 32, 52, 81, 119, 168, 231, 307, 400, 510, 639, 788, 959, 1154, 1375

Ich würde die Zahlenreihe gern erweitern ohne die Kurve zu verändern. Sie ist leider nicht linear.

...zur Frage

Gewichtete lineare Regression Formel?

Hallo,

ich habe den Vektor x und den Vektor y. Aus dem Vektor x bilde ich die Matrix A, wobei x die erste Spalte ist und in der zweiten Spalte jedes Element gleich 1 ist. Jetzt habe ich eine Funktion "bdcSvd" in meiner Programmiersprache, die aus der Matrix A und dem Vektor y die Lösung berechnet.

Fragen:

1) Wie kann ich da die Gewichte einbringen? Geht das überhaupt, werden die in der Matrix A oder im Vektor x mit eingebracht? Wenn nein,

2) wie ist die Formel, um aus A bzw. x und y (und einem Vektor w für die Gewichte?) die Lösung zu berechnen? Oder sollte man dafür einen raffinierteren Algorithmus verwenden (dann müsste ich danach suchen)?

Danke

...zur Frage

wie soll ich hier e bestimmen (mathe e funktion)?

wir hatten bis jetzt nur Log a (b) oder lg (b) dran und wenn ich nach lösungen gucke kommt nur was mit ln aber da hab ich kp was das is

...zur Frage

Kann mir jemand helfen?

Ich soll ein Struktogramm für diese Aufgabenstellung erstellen: Erstellen Sie einen Algorithmus, der den Benutzer nach zwei Zahlen Z1 und Z2 fragt und der anschließend ausgibt, ob

• Z1 größer als Z1 ist, oder

• Z1 kleiner als Z2 ist, oder

• beide Zahlen gleich sind.

Mein Struktogramm sieht so aus:

Bei der Auswertung im Programm bekomme ich immer Fehler und ich weiß nicht was an meinem Struktogramm falsch ist:

...zur Frage

Java, bei falscher Eingabe erneut fragen?

kann mir bitte jemand einen Java-Code für folgende Funktion schreiben, denn ich find keine Lösung dafür (Bin Anfänger und habe mir selbst eine Aufgabe gestellt um mein Können zu testen, aber ich verstehe es nicht).

Kunde auffordern Zahl einzugeben
Zahl(Quadrat) und ausgeben
Kunden fragen ob er erneut eine Zahl berechnen will „0“ für ja, „1“ für nein
bei „0“ Schritt 1 wiederholen
bei „1“ System beenden und „Auf Wiedersehen“ ausgeben

Das bekomme ich alles hin mit Schleife und If Funktion, aber nun Folgendes Problem:

6: bei jeder anderen Zahl „Ungültige Antwort“ ausgeben und zu Schritt 3 springen.

also falls das nicht verständlich war, wenn der Kunde nicht 0 oder 1 eingibt erscheint die Aufforderung von Schritt 3

Ich hoffe ihr wisst eine Lösung.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen