オーダー記法：ちょっとしたクイズ 続き - okamoto7’s blog
数日前に出した「オーダー記法：ちょっとしたクイズ」ですが，いろいろコメントをいただきました．ありがとうございます． たぶん聞き方が悪かったのかと思いますが「どこがまちがっているでしょう？」という問題なので，どこが間違っているのか，その箇所をピンポイントしてもらいたいのです． 例えば， いまからひらがなを五十音順で書きますがどこか違います．どこがまちがっているでしょう？ 「あいうえおかなくけこ」 ならば，まちがっている箇所は「な」です．理由はそこが「き」でなくてはならないからです．(例としてかなり不適切だと思いますけど，これぐらいしか思いつかなかったので．) と，こんな感じで，どこが間違っているのかピンポイントしてもらいたいのです．1つ1つ等式や不等式を追っていったとき，どのステップの等式か不等式が間違っているのか，と．そしてどうしてなのか，と．言い方を変えると，ではどこまでは証明があってる
2007-10-12
1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています． (真実は 1+2+...+n = n(n+1)/2 なので．) どこがまちがっているでしょう？というのがクイズです． 証明 nに関する数学的帰納法． n=1のとき，左辺は1で右辺はO(1)．1=O(1)なので成立． n>1のときを考えると，1+2+...+n=(1+2+...+(n-1))+n = O(n-1)+n = O(n)+n = O(n)． ここで，「1+2+...+(n-1)=O(n-1)」という帰納法の仮定を用いた． 証明終 このクイズはいろいろ示唆に富んでると思うのです．考えてみてください． (誰に向かって言ってるのか不明ですが．) 数学セミナー 2007年 11月号 [雑誌] 出版社/メーカー: 日本評論社発売日: 2007/10/12メディア: 雑誌 クリック: 4回この商
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
