ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

順序集合を並べるアルゴリズム

たいした内容ではないのですが、また数学のネタです。

今日は脳みそのコンディションが悪いので、読むに耐えないクソ記事になっているかもしれないですが…。

半順序関係が与えられた集合に対して、その半順序関係の情報に基づいて一列に並べるアルゴリズムについて考えていました。

その集合は“有限”の集合であると但し書きしないといけませんね。
なんか全部、有限であることが前提みたいに考えてしまうのは、情報系の人間の悪い癖だと思います。


さてしかし、普通、全順序関係じゃないと一列に並べられないんじゃないかということなのですが、

ここでは任意の元x,yについて、x <= yという順序関係があるとき、yは必ずxの右(上でもいいからとにかく大きい側の方向を定める)に来るという条件を充足するように、半順序集合の全ての元を一列に並べることを、一列に並べることとします。


つまり、大小比較できない二つの元については、どんな順番でもいいから無理やり一列に並べて、
大小比較できる二つの元については確実に、大きい元が大きい側になるように並べるということです。


このような一列を生成するアルゴリズムを、考えたわけなのですが、アルゴリズム自体はクソ簡単なものです。

そもそも私は難しいアルゴリズムを考案できるほどの脳みそがないので…。

続きを読む

tag: 数学 集合 順序 関係 アルゴリズム 計算 帰納法 証明 地図

計算量のO記法について解ってきたりきてなかったり

よくアルゴリズムの計算量(時間計算量)をO記法で書いているのを見ますが、あれってよく解らなかったんですよね。

O(n)とか、O(n^2)とか…。

しかし、最近、解ってきたような気がしないでもないので、そのまとめを記します。




時間計算量について

まず、時間計算量についてです。

これは要するに処理に要する時間なのですが、無論そんなものはマシンの性能に依存します。

まぁそれでも、逐次処理なら機械語にしたあと、
すべての処理に必要なクロック数をみて、それを時間計算量にすればマシンに依存はしないんでしょうけども、コンパイラ等の処理系には依存します。

また、いちいち機械語にしないと必要なクロック数というのはわかりません。


ではどうすればいいのか。
しかし、みなさん考えてみてください。

厳密に時間計算量を求めようとするからうまくいかないのです。

もっとアバウトに、アバウトに考えてみると、処理するデータの個数と処理時間がどのように関係しているのか?

それだけわかれば十分なのです。
(十分なのか!?)
続きを読む

tag: 計算量 アルゴリズム 処理速度

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。