- PR -

O(1) 操作

1
投稿者投稿内容
暁
大ベテラン
会議室デビュー日: 2006/06/28
投稿数: 116
投稿日時: 2007-03-24 15:25
開発の前準備として.NETの文法を勉強中です。
ヘルプドキュメントを参照しながら.NET Framework クラス ライブラリを調べているのですが、
理解できない表現に出くわしたため困っています。

分からないのは「O(1) 操作」という用語です。
この「O(1) 操作」とはどのような操作なのでしょうか？
前提に何らかの操作手続きが必要なのでしょうか？

どなたか教えていただけませんでしょうか？
よろしくお願いします。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2007-03-24 15:31
引用:

暁さんの書き込み (2007-03-24 15:25) より:
分からないのは「O(1) 操作」という用語です。
この「O(1) 操作」とはどのような操作なのでしょうか？

文脈が分からないので、推測になりますが、ランダウの記号である、いわゆる「ラージオー」ではないでしょうか。
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7
O(1)は、個数によらず一定の時間や手間がかかる操作、という意味です。
O(n)は、個数(n)に比例して時間や手間がかかる操作、という意味です。

--
unibon {B73D0144-CD2A-11DA-8E06-0050DA15BC86}
暁
大ベテラン
会議室デビュー日: 2006/06/28
投稿数: 116
投稿日時: 2007-03-24 20:11
回答ありがとうございます。
引用:
unibonさんの書き込み (2007-03-24 15:31) より:
文脈が分からないので、推測になりますが、ランダウの記号である、いわゆる「ラージオー」ではないでしょうか。

一部のみしか記述せずすみませんでした。この表記はArrayList.Count プロパティにあり、以下の文でした。
「このプロパティ値を取得することは、O(1) 操作になります。」
プロパティの解説文の最後に、思い出して追加したように記述されていました。

指摘を受けてリンク先を参照し、改めて見返してみますと、
確かにラージオー（私はビッグオー記法と覚えていました）を示したもののように見えます。
私がO(1)という表記を知らなかったことに加え、操作という言葉に引っかかってか、O-記法だとは考えもしませんでした。
また、今回初めてランダウの記号という言葉を知ることが出来ました。

引用:
O(1)は、個数によらず一定の時間や手間がかかる操作、という意味です。

なるほど。分かりやすい説明をありがとうございます。
ArrayList.Countの例で言えばつまり、ArrayList内の要素をいちいち数え上げるのではなく、
記憶領域のどこかに数を保持しておいてそれを返す操作ですよと明示しているというところでしょうか。

でも分かった上でも
「O(1) 操作になります」
は分かりにくい表現だと感じてしまいます。
そう感じているのは私だけかもしれませんが。。。

unibonさんありがとうございました。
明確な回答を頂き、すっきりしました。
なちゃ
ぬし
会議室デビュー日: 2003/06/11
投稿数: 872
投稿日時: 2007-03-24 22:09
引用:

暁さんの書き込み (2007-03-24 20:11) より:
指摘を受けてリンク先を参照し、改めて見返してみますと、
確かにラージオー（私はビッグオー記法と覚えていました）を示したもののように見えます。
私がO(1)という表記を知らなかったことに加え、操作という言葉に引っかかってか、O-記法だとは考えもしませんでした。

私も言葉としてはビッグ・オーと覚えてた様な気がしないでもないです。
確かにぴんと来ない人もいるでしょうから、説明がないのはやや不親切ではありますね。

一応、コレクションからみでO(?)が出てくると、常識的に（といえるのかどうかは分かりませんが）
これくらいしか思い浮かばないので、まあ微妙なところですが。
※「O(1)」を最初に見てしまったのが運が悪かったのかも。

でも、Oという記法自体を知らない人はいっぱいいてますね。
よねＫＥＮ
ぬし
会議室デビュー日: 2003/08/23
投稿数: 472
投稿日時: 2007-03-24 23:50
私は、単にオーダーとして覚えていますね。
数学の世界でランダウという人が広めた記法なのですね。これは今知りました。

たいていのアルゴリズムの本などで計算量を表現するために使用しています。
アルゴリズムの勉強や情報処理試験の勉強をしたことがあれば、
見聞きして知っている内容かと思います。
「O(〜)の操作」という言い方も多くの場面で見かけますので、
その説明が不適当とまではいえないかと思います。
暁
大ベテラン
会議室デビュー日: 2006/06/28
投稿数: 116
投稿日時: 2007-03-26 00:11
なちゃさん、よねＫＥＮさんありがとうございます。
引用:
なちゃさんの書き込み (2007-03-24 22:09) より:
一応、コレクションからみでO(?)が出てくると、常識的に（といえるのかどうかは分かりませんが）
これくらいしか思い浮かばないので、まあ微妙なところですが。
※「O(1)」を最初に見てしまったのが運が悪かったのかも。

確かに、教えていただいた後ではこれしか思いつかなくなったのですが、
O(1)を知らなかった時点では想像すらつきませんでした。（コレクションだから……とも気づけませんでした）
O(1)とO(n)が併記されている箇所もありました。確かにこちらを先に見ていれば悩まなかったと思います。
引用:
よねＫＥＮさんの書き込み (2007-03-24 23:50) より:
たいていのアルゴリズムの本などで計算量を表現するために使用しています。
アルゴリズムの勉強や情報処理試験の勉強をしたことがあれば、
見聞きして知っている内容かと思います。
「O(〜)の操作」という言い方も多くの場面で見かけますので、
その説明が不適当とまではいえないかと思います。

この表現が、ソートアルゴリズムの計算量を表すために使用されているのを見たことはありました。
ただ、私の見た本にはO(1)がおそらく記述されていなかったのだと思います。
アルゴリズムの入門書的な本だったので記述をはしょっていたのかもしれません。

今回のことで、知識に穴があいていたことに気づけてよかったです。
O(1)で悩んだ時間は確かに無駄でしたが、皆さんからの書き込みで結果的に良い知識を得ることが出来ました。
回答くださった皆さん、ありがとうございました。助かりました。
1

スキルアップ／キャリアアップ（JOB@IT）