Theorie 4 Fragen zur Induktion

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Theorie 4 Fragen zur Induktion

Beitrag von Hans123 » 26. Jun 2017 09:43

Servus,

ich habe mal eine Frage zu den Beispielen und den dortigen Induktionsanfängen. Da wird immer argumentiert, dass nach 0 Iterationen das A[a][0]...A[a][-1] Element quadriert/addiert/was auch immer wurde. Das -1te Element existiert ja aber nicht (es kann ja auch nach Definition eines Arrays gar nicht existieren), ihm wird dann im Blatt in Beispiel 3 zugewiesen, dass das der leeren Menge entspräche. Allerdings ist ja das nullte Element durchaus da (also die Menge ist ja dann eben nicht leer, außer das ist so definiert, das steht dann allerdings nirgends)

Wäre es hier nicht sinnvoller etwas in der Art zu sagen: nach 0 Iterationen ist man die Schleife noch nicht durchgelaufen, demnach wurde noch kein Element ausgelesen, die Summe (oder was auch immer) ist immer noch null, was korrekt ist?

Edit: zur Komplexitätsklasse bei Beispiel drei auch noch ne Frage: Das was da angegeben ist, ist ja eigentlich keine wirkliche Komplexitätsklasse oder? Also O(n+ Summenausdruck). O(n^2 / n*m) wäre doch eigentlich richtig.

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorie 4 Fragen zur Induktion

Beitrag von invariant » 26. Jun 2017 10:37

Hallo,

zu den Induktionsanfängen:
Mit A[n][0]...A[h-1] sind die Elemente A[n][x] gemeint mit x Element [a,b] mit a = 0 und b = h-1 also {x | a <= x <= b} - wenn a > b gilt, was bei a = 0 und b = -1 ja der Fall ist, ist das die leere Menge. Nach der Iteration h = 0 wurde noch kein Element quadriert, das ist also die Aussage die wir treffen wollen.

Sorry, dass es jetzt einfach so im Text ist, aber tex scheint im Forum nicht mehr zu funktionieren.


Dazu noch - finde akut nichts besseres:
https://de.wikipedia.org/wiki/Intervall_(Mathematik)

zur Komplexität:

Warum sollte das keine Komplexitätsklasse sein?

Gruß

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Theorie 4 Fragen zur Induktion

Beitrag von Hans123 » 26. Jun 2017 10:53

Ah so ist das gemeint. Danke!
(Ist meine Formulierung denn an sich auch korrekt oder sollte das so sein, wie es auf dem Blatt gemacht wurde?)

Zur Komplexität:
Also natürlich ist das eine Komplexitätsklasse, nur dachte ich ja, der Sinn der O/Omega/Theta Notation wäre es gewesen, direkt erkennen zu können, um was für eine Komplexität es sich handelt. Man streicht ja hierbei nicht umsonst alle Konstanten etc. weg.
Durch diesen Summenausdruck geht halt diese schnelle Einsicht verloren, also warum hat man hier statt O(n + Summe) nicht einfach O(n*m) gewählt? Das wäre ja aufs gleiche hinausgelaufen, allerdings ein wenig direkter ersichtlich. (also mir fällt es schwer einen Mehrwert in dieser hier gewählten Notation zu sehen)

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorie 4 Fragen zur Induktion

Beitrag von invariant » 26. Jun 2017 10:59

Hallo,

Sie könnten die Summe natürlich auch nach oben bzw. unten abschätzen. Dafür müssen Sie aber darauf achten dies korrekt zu tun:

die Summe der n veschiedenen m_i (Tex würde nun helfen...) lässt sich nach oben abschätzen durch:

n*max{m_1....m_n} bzw. nach unten durch n*min{m_1...m_n}

Natürlich sind auch andere Klassen denkbar. Allerdings müssen Sie darauf achten in dem Fall ihr verwendetes m auch zu definieren.

Hoffe das hat es geklärt.


Gruß

Antworten

Zurück zu „Archiv“