Montrez que si $ d (n) $ est $ O (f (n)) $, puis $ ad (n) $ $ est $ O (f (n)) $, pour toute constante $ A> 0 $?

Question

montre que si $ d (n) $ est $ o (f (n) $) $ , alors $ ad (n) $ est $ O (f (n) $) $ , pour toute constante $ a> 0 $ ?

Cela doit-il être montré par induction ou est-il suffisant de dire:

let $ D (n)= n $ qui est $ o (f (n) $) $ .

donc $ ad (n)= un $ qui est trivialement $ o (f (n) $) $

Answer 1

Non, il ne suffit pas de dire "let $ d (n)= n $ qui est $ o ( f (n)) $ . Par conséquent $ ad (n)= un $ qui est trivialement $ o ( f (n)) $ ". Bien que cela soit un moyen raisonnable de comprendre rapidement la proposition, elle n'est ni suffisante ni nécessaire. Il ne peut être considéré comme une preuve. Cela peut facilement conduire à un malentendu s'il est communiqué.

à montrer que "si $ D (n) $ est $ o (f (N)) $ , alors $ ad (n) $ est $ o (f (f (n)) $ , pour toute constante $ a> 0 $ ", appliquons les définitions pertinentes.

$$ \ commence {align *} d (n) \ text {is} o (f (n)) & \ Longrightarrow \ limsup_ {n \ to \fty} \ dfrac {| d (n) |} {f (n)} <\ \ \\ \ Gauche (\ Text {depuis} \ LIMSUP_ {N \ TO \ \FTY} \ DFRAC {A | D (N) |} {F (N)}= A \ LIMSUP_ {N \ TO \ \ \ \ DFRAC {| D (N) |} {f (n)} \ droite) & \ longrightarrow \ limep_ {n \ to \ infty} \ dfrac {A | d (n) |} {f (n)} <\ \\ \\ & \ Longrightarrow \ limsup_ {n \ to \fty} \ dfrac {| annonce (n)} {f (n)} <\ \ \\ & \ \ longrightarrow ad (n) \ text {is} o (f (N ))). \\ \ fin {align *} $$

La preuve ci-dessus est rigoureuse, bien que ce soit à peine la façon dont nous comprenons que les humains comprennent la proposition. Voici une autre approche.

$$ \ commence {align *} d (n) \ text {is} o (f (n)) & \ Longrightarrow | d (n) | \ texte {est limité ci-dessus par} cf (n) \ texte {quand $ n $ est assez grand pour une constante} c \\ & \ Longrightarrow | AD (n) | \ Text {est délimité ci-dessus par} ACF (n) \ Text {quand $ n $ est assez grand pour une constante} c \\ (\ Text {let} c '= AC) \ \ \ \ longrightarrow | ad (n) | \ Text {est limité ci-dessus par} c'f (n) \ text {quand $ n $ est assez grand pour une constante} c '\\ & \ Longrightarrow ad (n) \ text {is} o (f (n)). \\ \ fin {align *} $$

L'approche ci-dessus peut être considérée comme une preuve parmi les personnes qui connaissent les affaires. C'est probablement le moyen de comprendre également la proposition. Vous pouvez imaginer que le graphique de $ cf (n) $ se situe au-dessus du graphique de $ D (n) $ , et, par conséquent, le graphique de $ ACF (n) $ est au-dessus du graphique de $ ad (n) $ .

Answer 2

Ce n'est pas difficile.Une signification de $ D (n)= O (f (n)) $ est $ \ lim_ {n \ to \} \ frac {d (n)} {f (n)}= C $ quel $ C $ est constant.Par conséquent, $ \ lim_ {n \ to \ft} \ frac {A \ fois d (n)} {f (n)}= A \ fois C $ .Par conséquent, $ a \ fois d (n)= O (f (n) $) $ .

Answer 3

Écrivez la définition de Big-o.

à partir de ce moment-là, c'est des mathématiques triviales.

Les hypothèses que vous avez faites dans votre question indiquent que vous n'avez pas examiné la définition de Big-O, c'est pourquoi vous devez le faire en premier.