- ベストアンサー
「O(n)」は何と読みますか？
アルゴリズムの計算量を表すビッグオー記法の読み方を教えて下さい。 私は書籍で勉強しただけなので読み方が分かりません。 「O(n)」は何と読みますか？ 「おーのえぬ」でしょうか「おーえぬ」でしょうか、 あるいはまた別でしょうか？ ・自分はそうよんでいる ・学校でそう習った・先生はそうよんでいた ・サイト・書籍にそう書いてあった など根拠も付け加えていただけるとありがたいです。 よろしくお願いします。 回答例 ・自分は「O(n)」を「おーのえぬ」と読んでいる。正しいかどうかは知らない ・「URL」のサイトに「おーえぬと読む」と書いてあった
- pringlez
- お礼率99% (2344/2366)
- その他（プログラミング・開発）
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
関連するQ&A
- ビッグオー記法の読み方。
ビッグオー記法の読み方を教えて下さい。 例えば「O(n)」は何と読みますか？ 「おーのえぬ」でしょうか「おーえぬ」でしょうか、 あるいはまた別でしょうか？ ・自分はそうよんでいる ・学校でそう習った・先生はそうよんでいた ・サイト・書籍にそう書いてあった など根拠も付け加えていただけるとありがたいです。 この点について教えて下さい。 よろしくお願いします。
- 締切済み
- 情報工学
- Ｏ記法の値について
アルゴリズムの計算量を示すのにＯ記法というのがありますが、Ｏ記法って定数係数や次数の低い係数を無視しますよね。 例えば、計算量が次の式になる場合とか。 １．３ｎ＋２ → Ｏ（ｎ） ２．５ｎ''＋３ｎ＋５ → Ｏ（ｎ''） （ｎ''はｎの２乗） ３．２ｎ'''－４ｎ＋３ → Ｏ（ｎ'''） （ｎ'''はｎの３乗） どうして、定数係数や次数の低い係数を無視するのでしょうか？
- ベストアンサー
- その他（プログラミング・開発）
- 数のサイズのO記法について
代数学の勉強をしています。O記法についてわからないところがあります。 「a,b∈N,a,b≦nとしk:=[log(n)]+1とする。 加法a+bの計算に対するビット演算の数はO(k)で 乗法a・bに対してはO(k^2)である。 もし高速乗算アルゴリズムが使用されれば、乗法 はO(klog(k))にまで改良することができる。」 とあるのですが、加法がO(k)、乗法がO(k^2)と表せるのはO記法の考え方からわかりました。 しかし、「高速乗算アルゴリズムが使用されれば、乗法はO(klog(k))にまで改良することができる」 というところがどうしてそうなるのかがわかりません。 ※logの底は2です。
- ベストアンサー
- 数学・算数
- 漸化的計算量のオーダー記法O表記について
漸化的計算量のオーダー記法O表記について オーダー記法Oでの表記の仕方って、ようするにnをn→∞とした時に、一番大きくなる項を抜き出しきて、n→∞の時、増加量が微少な係数は無視をする。という考え方でいいんでしょうか？ 例えば 1000*(2^n)+0.5(n^n)=O(n^n) nlogn+n√n=O(n√n) n^2.01+(n^2)log(n^2)=O((n^2)log(n^2)) であってますか？
- ベストアンサー
- その他([技術者向] コンピューター)
- 対数logについて
対数logについて 基本情報処理技術者試験の勉強をしているのですが、 オーダ記法のところで、よく使われる表現として O(1) O(log n) O(n) O(n log n) O(n^2) ←計算時間小 計算時間大→ という五つの表現が紹介されているのですが、 このうち対数logを用いた物が理解できません。 例えば0(n)は、データ量nが2倍に増えれば計算時間も2倍になるということですよね。 しかしO(log n)だとどういう考え方になるのかわかりません。 対数についてもまだ理解できていないので、 対数のことから教えていただけないでしょうか。回答お待ちしてます。
- ベストアンサー
- 情報処理技術者
- Nlog2N=10^6の途中式について
数学の対数およびアルゴリズムの計算量の勉強をしておりますが、 Nlog2N=10^6という式において N≒60000となると記載があるのですが、 これはどういった展開でなるのでしょうか？ いくつかの公式を当てはめてみましたが、 上手く計算できませんでした。 もしくは、関数電卓を使わないと解けないレベル なのでしょうか？ ご教授お願いいたします。
- ベストアンサー
- 数学・算数
- 時間計算量とオーダーに関する問題がわかりません
1.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、F(n)=2^(2n)であるとする。 このとき、f(n)がO(2^n)でないことを示しなさい。 2.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、f(n)=c^(2n)であるとする。ただし、CはC>1の実数とする。このとき、F(n)がO(c^n)であるといえるか否かを示しなさい。 この二つの問題ですが、全然分かりません。 導出方法を教えてください。お願いします。
- ベストアンサー
- 数学・算数
- N2O4⇔2NO4のΔGを教えてください！
私の調べた資料で標準生成自由エネルギーはそれぞれ、 N2O4：97.82kJ NO2：51.1kJ となっていました。この値からN2O4⇔2NO4の反応におけるΔGを計算すると2×51.1－97.82＝4.38kJとなると思うのですが、ウィキペディアを見てみたところ45.53 kJ/mol となっていました。ウィキがおかしいのな？とも考えたのですがこのサイトで同反応の別の話に対する回答中にもΔG＝45.53 kJ/molとしているものを見つけ悩んでいます。どなたかお願いします。
- 締切済み
- 化学
- 計算量オーダーについて O(1/n)オーダー？
こんにちは、c#初心者です。 今回は計算量オーダーの話なので、基本的に言語は関係ないと思います。 計算量オーダーの基本的な部分は分かるのですが、O(1/n)オーダーのアルゴリズムは（今のところは）まだ見かけないというか、名前程度しか知らないので、これに関しては無知です。そこで、この場合はどういうオーダーになっているのかという質問です。 質問は３つあります。 １）この一連の処理はO(1/n)オーダーになっているか？ int count = 1000 / length; // lengthは正の整数 for ( int i = 0; i < count; i++ ) Do(); // O(1)オーダーの処理 ２） （１がO(1/n)の場合）繰り返す処理がO(n^2)になった場合に、この一連の処理はO(n)オーダーになるのか？ int count = 1000 / length; // lengthは正の整数 for ( int i = 0; i < count; i++ ) Do(); // O(n^2)オーダーの処理 ３）配列型のコレクション（コレクションって、c#の呼び方だったっけ？） [c#] List<T>,[c++] Bector, [Java] ArrayList(だったっけ？)のようなクラスのAddメソッドのオーダーは？ //Addメソッドの中身 if ( Capacity == Count ) Expand(); // Expandは配列の容量を２倍に拡張するO(n)処理とします。 array[Count++] = item; 以上です。 補足で、２）については大学の教授に「一回でもO(n^2)の処理が呼び出されたら、O(n^2)オーダーになる」と言われましたが、納得いかないです。確かに、O(1/n)オーダーの処理の後にO(n^2)オーダーの処理を行えば、そうなるのは納得いくのですが……という感じです。教授が読み間違えたとは考えにくいですが（確かにちょっと忙しそうでしたが）、念のため質問です。 それと、３）はよくある配列型のコレクションのまねです。「もし内容物が容量一杯になれば拡張→追加」を繰り返すとした場合です。ExpandメソッドのオーダーがO(n)なので、単純に計算すればO(n)オーダーになるのですが、呼び出される頻度が「(拡張された容量)回に１回」です。 例えば、容量が４ずつ拡張されるとすれば、「４回に１回」拡張が必要になり、１０ずつ拡張されるとすれば、「１０回に１回」の拡張が必要です。この場合、どう考えても全体として定数で割っているだけなので、O(n)オーダーのままになるのは明白なのですが、今回は容量２倍とさせていただきました。すると拡張の頻度は「（さっきまでの容量）回に１回」の頻度で、容量に反比例し、直感的にはO(Count / Capacity) = O(1)オーダーに見えるのですが、この判断は正しいでしょうか？ 皆さんのご意見を伺わせてください。
- ベストアンサー
- C・C++・C#
- データ構造とアルゴリズムの問題が分かりません。
以下の問題で悩んでいます。 １ 配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。 ２ 配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。 ３ データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。 ４ アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。 ５ データを検索する操作のほうが多い場合と、データを追加する操作が多い場 合、 「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。 １は、挿入と削除はO記法で表せたのですが、追加が分かりませんでした。 ２は配列の利点はランダムアクセス可能な点と任意のデータをすぐに扱える点の２点 リストの利点は扱うデータを自由に変えられる点の１点しか思いつかず、欠点はよく分かりませんでした。 ３、４、５も理由をつけて説明しろと言われたら無理です。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- クアデルノラミースタイラスペン FMVSP3は、富士通FMVシリーズ専用のスタイラスペンです。
- 富士通FMV以外のデバイスでは使用することができません。
- 富士通FMVユーザーにとっては便利なアイテムですが、他のメーカーのノートパソコンやタブレットでは使用することができません。
お礼
「えぬのおーだー」ですか。 そしてリンクのWikiの一番下に以下が書いてありました。 『…と書いて、「n² のオーダーである」と言い、』 これですね！ ありがとうございました