Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Landau-Notation | Beweise
Druckversion
Druckversion
Autor
Universität/Hochschule J Landau-Notation | Beweise
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 145
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-05-18


Hallo,

Ich habe folgende Aufgaben:

Beweisen oder Widerlegen Sie (ohne Grenzwerte, nur mit der Mengendefinition):

(1) \(3n^{3} + 8n^{2} + n \in \mathcal{O}(n^{3})\)
(2) \(2^{n} \in \mathcal{o}(n!)\)

Diese Aufgaben sind relativ neu für mich, weshalb ich mich noch ein bisschen schwer mit solchen Beweisen tue. Zur (1) habe ich die Frage ob mein Weg legitim ist, und zur (2) eine etwas allgemeinere:

(1) Ich muss zeigen, es existiert ein \(n_{0} > 0, C > 0\), so dass für alle \(n \geq n_{0}\) gilt: \(f(n) \leq C \cdot g(n)\)
Ich habe einfach \(n_{0} = 1\) definiert, dann ist ja \(3n^{3} + 8n^{2} + n \leq 3n^{3} + 8n^{3} + n^{3} = 12n^{3}\) also kann ich mir \(C := 12\) definieren. Weil für \(n_{0} = 1\) ist es ja egal was für eine Potenz n hat und für alles darüber ist die Summe größer. Stimmt das oder habe ich etwas falsch gemacht? Habt ihr sonst noch Allgemeine Tipps für solche Aufgaben?

(2) Ich muss zeigen, das für alle \(C > 0\) ein \(n_{0}\) existiert, so dass ... (bis auf FÜR ALLE C äquivalent zu (1))
Hier weiß ich leider gar nicht wie ich die Abschätzung anfangen soll. Ich darf mir ja kein festes C mehr wählen, weil es ja \(C > 0\) beliebig ist, richtig? Also muss ich zeigen, dass es für jedes C eben so ein \(n_{0}\) gibt. Ich würde mich über jegliche Hilfestellungen sehr freuen.

Danke für eure Aufmerksamkeit :)!

Mfg



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]