計算機科学・情報科学の本

**名無しさん＠お腹いっぱい。** · 2006/10/13(金) 20:57:25

ないから立てた

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 05:28:45

>>383
> >>380
> O-記法の厳密な意味を調べるんだ。ランダウの記号とかでググってみると良い。

そんなのは知ってるさ

> O-記法は、あくまで上界を示すものだから、下に凸だろうが変曲点があろうが
> 構わないんだよ。実際に、O(n^2)でも変曲点をもつようなアルゴリズムはある
> わけで。

変曲点の有無は何ら重要性がないから図に入れるべきでないと主張してるんだよ。
図とは本質的に重要な情報だけを入れれば良いのだ。

そもそも個々のアルゴリズムの時間計算量はイグザクトに決まるから
上界を示すO記法でなくΘ記法を用いるのが適切なんだが
慣習的にO記法で済ませている事がおおい。

例えば、O記法は上界を意味するからと言って、
「（Θ(n・log n）と分かっている）ヒープソートの最悪時時間計算量はO(n^2)だ」と言えば
O記法の使用法として論理的には正しいが「こいつ何も分かってないんじゃないの？」と馬鹿にされるのがオチ。

本質的にO記法が必要なのは問題自身の計算量の方だよ。
与えられた問題に対して最適の（つまり最も計算量の小さな）アルゴリズムが発見されているとは限らないからね。
例えばｎ次正方行列２つの積を求める問題の時間計算量はStrassenのアルゴリズムが発見される前まではO(n^3)のクラスであり、
それが発見された事でO(n^(log_2 7))のクラスに下がったわけだ。

> だから図は間違ってはいない。ただ説明用の図としては他の例を選んでも
> 良かったと思うけどね。

O記法が上界を意味するから間違っていないなんて言ったら
O(c^n)に対するグラフとして log n のグラフを示しても間違っていないという事だよ。

じゃあ、何の為にグラフを示すんだね？
O(f(n))に対するグラフはf(n)以下のグラフなら何を示しても間違いでないという事だ。
そんなグラフを見せる事に何の意味がある？

O記法は上界を表すだけだなんて詭弁を弄さずに、O(f(n))のグラフを示す事は何を伝える事が目的かを考えたまえ。
上界としてのf(n)の漸近的振る舞いを示し、f(n)の違いによって n　が大きくなるとどれほど違うかを学生に伝えるのが目的なんじゃないのか？

O記法は単に上界だからO(f(n))に対するグラフは漸近的にf(n)以下となるどんな関数のグラフでも良いなんてなったら何の意味もない。
上界だからこそ、そのオーダーに属し得る最大の関数のグラフを示すべきだろう。

そして線形（つまりO(n)）よりも計算が大変か容易かこそが何よりも伝えるべき事柄だよ。
それが下に凸な形か上に凸な形かという事で明快に表現されるという事だ。

はっきり言えば、何のスケールも示されていない完全に定性的なグラフではO(n^k)とO(c^n) （c, ｋ＞１）とはグラフの形だけでは明確に区別できない。
せいぜいO(n^2), O(n^3), O(n^4), ...　と段々と急増加するグラフを並べてO(c^n)はそれらより更に増加が激しいという様にして示す以外にない。

ここには例のグラフにあった変曲点なんて無意味なものが登場する余地はない。
変曲点の有無なんて計算量のクラスとは何も関係ないのだから。

計算量と関係のない変曲点を書いている一方で線形より遅いはずのO(n^k)のグラフが漸近的に上に凸になるように書いているから
「あのグラフを書いた教員は計算量について何も分かっていない」と批判してるんだよ。

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 09:21:27

俺はむしろノイズを入れた線をあえて描いておくべきだと思うね。
O(n^2)は、ちょうどn^2に比例した計算量だと思っている奴が多い
こと多いこと。実際にはそんなことは滅多にないわけで、だったら
説明の図もそうあるべきだと思う。

この人がそこまで考慮して作ったのかどうかはわからんが。いずれに
せよ、この図を使ってどう説明したかによるな。少なくとも、3本とも
綺麗な線で描いておくよりは誤解が少なくて済むと思う。

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 12:14:19

そろそろスレ違いということに気づいてほしい

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 18:49:41

では、この話題はこれで終了ということで。

**名無しさん＠お腹いっぱい。** · 2010/06/14(月) 01:09:54

>>385
> 俺はむしろノイズを入れた線をあえて描いておくべきだと思うね。
> O(n^2)は、ちょうどn^2に比例した計算量だと思っている奴が多い
> こと多いこと。実際にはそんなことは滅多にないわけで、だったら
> 説明の図もそうあるべきだと思う。

ふーん、計算量理論やアルゴリズム論をお前に習わなくて俺は幸運だったよ。

> この人がそこまで考慮して作ったのかどうかはわからんが。いずれに
> せよ、この図を使ってどう説明したかによるな。少なくとも、3本とも
> 綺麗な線で描いておくよりは誤解が少なくて済むと思う。

まず最も典型的なのを理解させるのが第一歩、一般的な場合を教えるのはその次の段階だと俺は考えてるがな。
典型的なケースさえ理解できん学生が一般的なものを理解できるなど、よほど特殊な人間（人はそういう人間を天才と言う）以外にはまず不可能。
ノイズの入った図からノイズを除去して本質を見抜いて理解できる学生なんて宮廷大クラスでもほとんどいない。

そんな問題以前に、O(n^k)として最も良く出て来るｋ＞1の場合のO(n^k)のグラフが横軸（当然だが問題サイズ n の筈）の大きい部分で上に凸、
つまり漸近的には線形時間のO(n)よりも高速になる形で書いてるのが致命的だね。
これは言い訳が不可能。
まさかO(n^(1/2))を示したなんて言わないだろうな。
O(n^(1/2))の問題やアルゴリズムなんてこのグラフを見る初歩的な段階では出会ってないのは確実だからな。

結局、今回の秋田県立大？のこのグラフを書いた教員は、３つのグラフを違った形で書けば良いぐらいしか考えずに書いたとしか思えんな。

さて、スレチだという批判もあるみたいだし、これだけ説明しても理解できんのなら相手にしても無駄だから、俺も終わりにしよう。

**名無しさん＠お腹いっぱい。** · 2010/06/14(月) 05:55:36

>>388
うぜえからさっさと帰れ

**名無しさん＠お腹いっぱい。** · 2010/06/16(水) 16:36:00

>>388
とっとと死ねやこのクソゴミクズカス

**名無しさん＠お腹いっぱい。** · 2010/06/16(水) 18:35:52

>>389 >>390
>>389 >>390