プログラミングの為の数学と算数 vol.2at TECHプログラミングの為の数学と算数 vol.2 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞのURL■項目テキスト468:デフォルトの名無しさん 06/03/11 00:31:55 >>464で、x番目に調べるまでの距離の総和をf(x)とすると、 f(2^n-1) = 2*Σ{i=1..(n-1)}(2^i-1) = 2*((2^n-2)-(n-1)) <= 2*2^n 2^(n-1) <= x <= 2^n-1のとき、 f(x) <= f(2^n-1) <= 2*2^n = 4*2^(n-1) <= 4*x よってO(x) 469:デフォルトの名無しさん 06/03/11 01:10:36 ＞＞４６８ なるほど。 助かりました。 ありがとうございました。 470:デフォルトの名無しさん 06/03/14 22:27:00 (0,1)における実数の集合が、可算無限集合ではないことを背理法と対角線論法を使って証明するやつだけど、 いまいち何やってるか分からないんだよね。 分かった気にはなるけど、どうもしっくりこないっつうかなんつうか。 他に証明方法とかあるのかね？ 471:デフォルトの名無しさん 06/03/14 22:38:27 >>470 有理数列と実数の部分集合に1対1の対応が作れる 有理数列は自然数→有理数の写像とみなせる 自然数→有理数の写像の濃度は アレフ0^アレフ0 ＝ 2^アレフ0 アレフ0 ＜ 2^アレフ0 （ある集合の濃度が N のとき、その冪集合の濃度は 2^N、 ある集合とその冪集合の間にはどうやっても全単写が作れない） なので、可算濃度＜実数の濃度 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch