初投稿だから無難な話をする(関数のオーダー)(続く)
こんばんは。初投稿です。
今回は僕が電卓で遊んでいた話をします。
僕はchromebookを外出するときに持ち歩くのですが、残念ながらsimカードが入っていないので外ではネットに繋がらず、pythonをいじったり電卓で遊んでいます。
僕は関数電卓を持っていないのでパソコンの関数電卓モドキを初めて見たときにはそれはもう感動したんですよね。
その時見つけたのが$x!$というもの。その頃僕はそれが階乗という名前で、整数に使えることは知ってたんですけど、なんとそこでは小数も使えたんですね。
もう感動して感動して３０分ぐらい遊んだんですけど、そこで気づいたことが２つ。
- でかくなるの早くね？？？
- 全然増えない数があるな？？？
幸い優秀な友達が周りにいるので訊いてみました。するとどうやら関数には強さというものがあるそうです。
この記事は全く無学の人が書いていますので厳密性はありません。無です。また、この記事では関数のオーダーについてだけ話します。
関数の強さ
関数の強さとはどれだけ早く大きくなるか、というものらしいです。例えば
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
y = 2x \\
y = x^2
\end{array}
\right.
\end{eqnarray}
$$
という２つの関数があったとします。
このときどちらのxがより早く大きくなるか？おわかりですね？$ x^2
$です。これが「関数の強さ」です。
もう一つぐらい例を出して関数の強さの話は終わりにしましょう。
$ \begin{eqnarray}
\left\{
\begin{array}{l}
y = x^2 \\
y = 2^x
\end{array}
\right.
\end{eqnarray} $
どちらがより早く大きくなるか...一目ではわかりません(理系の皆さんは黙っててください)
ここで使う考え方は「数学的帰納法」です。この名前覚えていますか？
$x = n$のとき、$2^n$が$n^2$よりも大きいと仮定します。このとき、$x = n+1$のときにもその大小関係が成り立つなら、$2^x$は$x^3$よりもいつでも大きいということがわかります。これが「数学的帰納法」です。
$2^x \geq x^2$(Aとおく)を数学的帰納法を用いて示す。($x\geq 3$)
$x = 4$のとき、$2^4 - 4^2 \geq 0$より、Aは成り立つ。
$x = n$のとき、 Aが成り立つと仮定する。
$x = n+1$のとき、両辺の差を取って
$$
2^{n+1}-(n+1)^2 = 2 \cdot 2^n - n^2 -2\cdot n -1\\
=2^n - n^2 +2^n -2\cdot n -1\\
$$
仮定より、$n^2-2^n$は正であるから、$2^n-2\cdot n-1$が正であること(Bとおく)を示せばよい。
$n=k$のとき、Bが成り立つと仮定する。(もう一回数学的帰納法を使います)
$n = k +1$のとき
$$
2^{k+1}-2\cdot (k+1)-1 =2\cdot 2^k - 2\cdot k -2\\
=2^k -2\cdot k -1 + 2^k -1
$$
仮定より、$2^k -2\cdot k -1$は正であるから、$2^k-1$が正であることを示せばよい。しかしまぁこれは自明である。わかりきっている。
したがって、Bは成り立ち、またAは成り立つ。
(証明終わり)
これでこの二つの関数が、どちらがより強いのかがわかりました。
こんな感じでいろいろな関数の強さを比べていくと、$x!$はかなり強い関数であることがわかってきます。$x^{10000000000}$よりも$1000000000^{x}$よりも強いです。証明はとても簡単なので気晴らし程度に示してみてください。
$$
$$
終わり。(このサイトの高校生向けって高校生向けじゃなくないですか????)
