Ich weiß, dass die Beziehung n = Big-O (1) falsch ist. Aber wenn wir Induktion mit Big-O verwenden, kann es bewiesen werden. Aber der Irrtum ist, dass wir Big-O nicht einführen können. Aber meine Frage ist, wie wir die Beziehung durch Verwendung der Konstanten widerlegen können.
Der falsche Beweis ist hier, bitte geben Sie mir den Beweis, dass er mit den Konstanten falsch ist. Ich bin verwirrt mit den Konstanten, ich weiß nicht, ob jede Beziehung, die im Beweis verwendet wird, eine unterschiedliche Konstante oder das Gleiche hat. Bitte erleuchte das Thema.
%Vor%Induktions-Hypothese: sei wahr: n-1 = O (1) Jetzt beweisen wir, dass n = O (1)
%Vor%Falsch bewiesen .. Ich möchte die Klärung des Irrtums in Bezug auf & lt; = und Konstanten, das heißt in der grundlegenden Definition von Big-O.
Hier ist ein großer logischer Irrtum versteckt:
%Vor%n ist eine Funktion und Ο (1) ist eine Menge von Funktionen. Es gibt auch keine Nummer (und Induktionsbeweise drehen sich darum, Dinge für einen ganzen Haufen einzelner Zahlen auf einen Schlag zu beweisen). Die Verwendung von Gleichheitszeichen wie n = Ο (1), ist eine informelle Abkürzung für f ∈ Ο (1), wobei f (x) = x .
Dieser Beweis verwendet den Irrtum der Zweideutigkeit auf zwei Arten:
Wenn Sie deutlicher sehen möchten, warum dieser Beweis fehlschlägt, ersetzen Sie n durch eine andere Notation für eine Funktion, f (wobei f (x) = x) und die Gleichheitszeichen mit Elementzeichen wo erforderlich Beweis macht immer noch Sinn.
Basisfall:
%Vor%Induktiver Fall:
%Vor%Es wird viel klarer, dass dies überhaupt kein Induktionsbeweis ist. Es ist nicht einmal ein gültiger Beweis, denn wir haben nur bewiesen, dass h ∈ Ο (1), was nichts mit g ∈ Ο (1) zu tun hat, da diese Funktionen sehr, sehr unterschiedlich voneinander wirken.
Bei der großen O-Notation geht es um Funktionen, also haben Aussagen wie 1 = O(1) keine Bedeutung. Was Sie hier beweisen, ist, dass wenn Sie eine beliebige n und die konstante Funktion f(x) = n verwenden, dann f = O(1) , was wahr ist und keinen Widerspruch ergibt. Es gibt kein Problem mit dem Beweis, das Problem ist, dass Sie die konstante Funktion f(x) = n mit der Funktion f(n) = n verwechseln. Für letzteres haben wir f = O(n) und wenn Sie versuchen, es mit Ihrer Methode zu beweisen, werden Sie sehen, dass es nicht funktioniert.
Eine Sache, die Sie hier verstehen müssen, ist, dass Big-O oder einfach O die 'Rate' bezeichnet, mit der eine Funktion wächst. Sie können die mathematische Induktion nicht verwenden, um diese spezielle Eigenschaft zu beweisen.
Ein Beispiel ist
%Vor%Durch einfache Mathematik impliziert die obige Aussage O (n) = 0, was nicht der Fall ist. Also würde ich sagen, verwende MI nicht dafür. MI ist geeigneter für absolute Werte.
Wenn Sie strenge Beweise für die Big-O-Notation benötigen, müssen Sie mit der -Formatdefinition von Big-O beginnen. O In einem Beweis kannst du nicht einfach O(1) + 1 = O(1) sagen. Sie müssen den Beweis in Bezug auf die formale Definition machen. Um zu beweisen, dass eine Funktion ( f(n) = n zum Beispiel) O (1) ist, müssen Sie eindeutige x0 und M finden, die mit der Definition übereinstimmen. Sie können dies durch Induktion demonstrieren, und Sie können auch einen Beweis durch Widerspruch machen, indem Sie die Definition verwenden, um zu zeigen, dass f(n) = n nicht O(1)
Genau wie Olathe in seiner Antwort sagte, können Sie nicht einfach Big-O-Sets und Funktionen hinzufügen. Beginnen Sie mit der formalen Definition dessen, was eine Funktion als Mitglied eines bestimmten Big-O-Sets klassifiziert.
Tags und Links complexity-theory big-o proof