Beim Beweisen und Widerlegen von Big O Fragen, die ausdrücklich die Definition zum Beweis und zur Widerlegung verwenden, lautet meine Frage, was mache ich richtig?
Zum Beispiel hast du eine Frage, die g (n) = O (f (n)) ist ... Um es zu beweisen, habe ich folgendes gemacht:
%Vor%Der Widerspruch, auf den ich dabei stoße, ist, wenn ich eine Frage der Widerlegung dieses Zeugs anwende
zum Beispiel
g (n) = O (F (n)) um es zu widerlegen, würde ich tun
g (n) & gt; = C (F (n)) und löse erneut nach C. Aber das führt mich zu der Annahme, dass großes O auf einmal bewiesen und widerlegt werden kann? was 100% falsch ist.
Verwenden von echten Zahlen (Beweisen)
%Vor%beide sagen, dass @ n = 1 und c = 3 der Algorithmus ist O (n ^ 2) und ist NICHT O (n ^ 2).
Kann mir jemand helfen, meine Verwirrung zu klären und mir helfen, eine gute algorithmische Lösung für große O-Fragen zu finden?
Keine Ihrer Techniken funktioniert. Beginnen wir mit der Definition von big-O:
f ist O (g) wenn es C gibt, so dass | f (x) | ≤ C | g (x) | für alle x ≥ N
Um zu beweisen, dass es "gibt", müssen Sie zeigen, dass die Dinge existieren. Im Falle von Big-O-Beweisen finden Sie normalerweise die Dinge, obwohl Existenzbeweise im Allgemeinen nicht konstruktiv . Um einen Beweis für eine Aussage "für alle" zu erstellen, tu so, als ob jemand dir bestimmte Werte gegeben hätte. Seien Sie vorsichtig, wenn Sie keine impliziten Annahmen über ihre Eigenschaften treffen (Sie können Eigenschaften explizit angeben, z. B. N & gt; 0).
Im Fall des Beweises von big-O müssen Sie das C und N finden. Zeige | g (n) | ≤ C | F (n) | für ein einzelnes n ist nicht ausreichend.
Für das Beispiel "n 2 +3 ist O (n 2 )":
%Vor%Um dies zu widerlegen, nimmst du die Negation der Aussage: zeige, dass es kein C oder N gibt. Zeigen Sie mit anderen Worten, dass für alle C und N ein n & gt; N so, dass | f (n) | & gt; C | g (n) |. In diesem Fall sind das C und N für "alle" qualifiziert, also tue so, als ob sie dir gegeben worden wären. Da n qualifiziert ist "es existiert", müssen Sie es finden. Hier beginnen Sie mit der Gleichung, die Sie beweisen möchten, und arbeiten rückwärts, bis Sie ein geeignetes n gefunden haben.
Nehmen wir an, wir wollen beweisen, dass n nicht O (ln n) ist. Täuschen Sie vor, wir haben N und C, und wir müssen ein n ≥ N finden, so dass n & gt; C ln n.
%Vor%Beweise von x & gt; 0 ⇒ e x & gt; x 2 und "n ist nicht O (lnn)" ⇒ "n ist nicht O (log bn)" als Übungen übrig.