Big O表記のBigとOとは何ですか？私は「定義を読みましたが、 O が「oh」と発音されているのかわかりません。たとえば、 O （n）は線形アルゴリズムの複雑さであり、nは演算の数である可能性があることを理解しています。しかし、 O とは何ですか？
コメント
- それ’英語のアルファベットの15番目の文字。 ‘はギリシャ文字の15番目の文字でもあります。
- 明確にするために：あなたは’を探しています O が（QやEなどの代わりに）使用される記号である理由、および O が他の記号に対してどのような意味を持っているか（ある場合）。
- @Joel：実際、それは’のオミクロンであり、それがこの特定の文字がなぜ選ばれたかについての手がかりです。
- この回答は、オミクロン理論に（正しくは）反論します。
回答
まあ、私の推測では、ウィキペディアと一致する順序です。
編集:(私自身（改善はありがたい））ドイツ語のウィキペディアの記事
大文字のO（実際には当時の大文字のオミクロン）は、順序（ドイツ語： “Ordnung von”）の記号として最初に使用されました。ドイツの数論者PaulBachmanは、解析的整数論に関する本の第2号に登場しました。この表記は、別のドイツの数論者であるEdmund Landauの業績により人気を博しました。この命名法は、今日、特にドイツ語の用語。
コメント
- 多くの数学者が言及している場合もありますが、それ自体は、もともとそうではありませんでした。 20世紀初頭の数論の本を読んでも、そのような説明はありません。それが何であるか、そして私は’ドイツ語を読んで、彼の考えが表記法について何であったかを理解することができません。
- @Jonathan：投稿が更新されました。
- とてもいいです！数論の本をすべて調べたところ、’どこにもOの説明が見つかりませんでした。 +1
- I ‘は、Oはあまり意味がないと言っているだけなので、常に順序と発音していました。
- 非常に有益です！しかしそれでも-なぜOはプログラマーによって’ oh ‘と発音されたのですか？
回答
「大きな」は「資本」を意味し、「O」は「複雑さの順序」のように順序を意味します。このように名付けられたのは、「複雑さの順序」をO（f（x））と書く慣習のためです。たとえば、大文字の「O」または「BigO」を使用します。 「誰もが」それが何を意味するのかを理解しているので、誰もそれについてあまり話しません。それを理解しても、複雑さの分析を理解するのに実際には役立ちません。
複雑さの分析を理解するために、topgun_ivardによって投稿されたリンクは開始するのに適した場所です。データ構造やアルゴリズムをカバーする優れた入門書も役立つ場合があります。
コメント
- I ‘申し訳ありませんが、バッハマン-ランダウ表記はドイツの数学者によって発明されたため、英語の単語にちなんで名付けられたとは思えません。実際、たとえによって発明されたとしてもアメリカの数学者なら、おそらくドイツ語にちなんで名付けられたでしょう。なぜなら、それが発明されたとき（1920年頃だと思います）、数学の国際言語はドイツ語でした。さらに、’ tでもリモートは複雑さと関係があります。
- @J ö rg：はい、しかし’それは、ドイツのwiki記事が起源であると主張している Ordnung です： de.wikipedia.org/wiki/Landau-Symbole#Geschichte
- @Ethel記事に小さな変更を加えて、投票できるようにしていただけませんか。あなたは確かに正しいです。投票する前に編集する必要があります。
- @Jonathan、私は’どのような小さな変更が必要か正確にはわかりません。先に進んで、必要な編集を行うことができますか？または、back2dos ‘の回答をそのままにしておくこともできます。優れた調査により、彼はとにかく最良の回答に終わったようです:)
- 、 面白い。スウェーデンでは、BigOhは通常”ではなく” ordo “（ラテン語で注文）と呼ばれます。 >
ordning “（スウェーデン語で注文を表す）
回答
O は注文を表します。
もともとは、ドイツの数学者PaulBachmannによって数論に関する本の第2巻 Die Analytische Zahlentheorie で紹介されました。 1894年に公開（p.401）。彼は、最初に表記を使用した式の後で、次のように述べています。
（…）wenn wir durch das Zeichen O（n）eindeGrösseausdrücken、deren Ordnung in Bezug auf n die Ordnung von n nichtüberschreitet（…）
私の翻訳：
（…）ここで、 O（n）という表記を使用します。 n を参照する次数が n の次数を超えない大きさを示します（…）
他の人が言ったこととは対照的に、彼のテキストには、これが実際にギリシャの首都オミクロンであることを示すものは何もありません。彼はギリシャ語とラテン語の両方の文字をたくさん使用しているので、「実際に伝える方法はありません。テキストで「Ordnung n log n 」などを継続して使用していることを考えると、それは明らかです。いずれにせよ「Ordnung」（疑わしい場合は「order」を意味するドイツ語）の略ですが、それでも派手なギリシャ語のOを使用したままにすることができます。
ただし、オミクロンの起源はの論文 Big Omicron and Big Omega and Big Thetaで関連する概念にオメガ（Ω）とシータ（Θ）の記号を導入したドナルド・クヌースによるレトロニムの可能性が高い 、または以前にオメガ記号を導入したハーディとリトルウッド。
コメント
- 興味深い。私はあなたが正しいと思います。 Landau ‘とBachmann ‘の両方の本で定義を調べたところ、実際にはa）ラテン語を使用しています。ギリシャ語のオミクロン、b）どちらも” Ordnung “という単語を使用し、c）Landauは明示的に次のように述べています。 ” Ordnung “を意味します。私は正直に立っています。
- より良い言葉を見つけることができますか？つまり、ドイツ人からですか？ Ordnung ist das halbe Leben！
- あなたの（正しい、賛成の、素晴らしい）答えの最初の文は次のようになっていると思います：’ Oは” Ordnung “（ドイツ語で”注文”） 。’この回答が他の読者の注意を引くのに役立ちます。
回答
この記事が気に入っています。これもお役に立てば幸いです！
記事のセクションを引用します：
大きなギリシャ文字
大きなOはよく誤用されます。 BigOまたはBigOhは、実際にはBigOmicronの略です。これは、漸近的な複雑さの上限を表します。したがって、アルゴリズムがO（n log n）の場合、上限がcn lognになるような定数cが存在します。
Θ（nlog n）（Big Theta）はそれよりも厳密にバインドされます。このようなアルゴリズムは、c1n log n < f（n）< c2n lognのような2つの定数c1とc2が存在することを意味します。
Ω（nlog n）（Big Omega）は、アルゴリズムにはcn lognの下限があると述べています。
他にもありますが、これらが最も一般的で、BigOが最も多いです。すべての共通。このような区別は通常重要ではありませんが、注目に値します。結局のところ、正しい表記法は正しい表記法です。
Big Oとは何ですか？
Big O表記法は、キーの成長率を下げることにより、アルゴリズムの相対的な複雑さを説明しようとします。キーファクターが無限大に向かう傾向がある場合のファクター。このため、漸近的複雑というフレーズをよく耳にします。そうすることで、他のすべての要因は無視されます。これは複雑さの相対的な表現です。
Big Oとは何ですか？
BigOはアルゴリズムのパフォーマンステストではありません。また、他の要因を無視する傾向があるという点で、概念的または抽象的です。ソートアルゴリズムの複雑さは、通常、重要な要素としてソートされる要素の数にまで減少します。これは問題ありませんが、次のような問題は考慮されていません。
メモリ使用量：あるアルゴリズムが別のアルゴリズムよりもはるかに多くのメモリを使用する可能性があります。状況に応じて、これは完全に無関係なものから重大なものまで何でもかまいません。比較のコスト：要素の比較は非常にコストがかかる可能性があり、アルゴリズム間の実際の比較が変わる可能性があります。要素の移動コスト：要素のコピーは通常安価ですが、必ずしもそうとは限りません。など
コメント
- 記事をリンクするだけでは’あまり役に立ちません。 ‘通常、スレッドに特に関連すると思われるセクションを言い換えたり引用したりすることをお勧めします。
- 反対票は本当に必要ですか？彼がリンクした記事は非常に関連性があり、私見は非常に役に立ちました。一方、投票数の多い回答は、ウィキペディアの記事へのリンクです。 +1は、集合精神の偽善を相殺します。
- -1、なぜなら、アーティスは非常に素晴らしく、よく書かれた記事でありながら、’質問とは何の関係もありません。
- @Jorg、この記事で問題が解決するとは言いませんでしたが、これらの概念を調べたときに役立つことがわかったので、共有しました。
- @topgun_ivard：では、リンク切れになった場合はどうなりますか？言い換えると、1）このスレッドのオーディエンスは、リンクのコールズノートバージョンを取得でき（時は金なり）、2）投稿がデッドリンクに無関係に表示されないようにします。
回答
編集：私が間違っていることがわかりました。それでも、これは誰かが記号をまっすぐに保つのに役立つかもしれないので、私はそれを削除するつもりはありません。
実際には、ラテン文字ではありません ああ、それはギリシャ文字のオミクロンです。残念ながら、これら2つはまったく同じグリフを持っているため、時間の経過とともに元のバージョンが破損し、現在はああ。
記号の選択は実際には特別な意味はありません。ニーモニックデバイスとして選択されました：
- Omicron にはMICROという文字が含まれており、Omicron記号のセマンティクスはおおよそ「より小さい」を意味します
- Omega にはMEGAという文字が含まれています、およびオメガ記号のセマンティクスは、おおよそ「より大きい」を意味します
- シータ（Θ）は、等号に少し似ています、およびシータ記号のセマンティクスは、おおまかに「等しい」を意味します
それはそれです。それは本当の意味はありません。それは、もしあなたがあなたがセマンティクスをもっと覚えるのを助けるためにasily。
コメント
- あなたのニーモニックの提案を信じたいのですが（それは本当にクールなアイデアです）、私は見る必要がありますこれがバックマンの実際の本来の意図であるといういくつかの証拠。それを提供してください。’あなたに+1します。
- @JonathanHenson：どうやら、私はKnuth教授に惑わされました:-)
回答
“f（x）is big-oh of g（x）”
です関数の成長を予測する数学的な方法。
fとgを、整数のセット、または実数のセットから実数のセットまでの関数とします。 | f（x）|のような定数Cとkがある場合、f（x）はO（g（x））であると言います。 < = C | g（x）| x> kの場合
これは「f（x）はg（x）のbig-oh」と読みます
big-Oは後にランダウの記号と呼ばれることもありますドイツの数学者エドマンド・ランダウ。それ以上の意味はないと思います。同様のビッグオメガとビッグシータの表記法もあります。記号は、高校の平面幾何学で三角形の角度を示すためにシータを常に使用するのと同じくらい任意です。クラス。
修正 @ back2dosは、順序を参照するものとしてOに満足のいく説明を提供しました。仕事。彼の答えを見てください。
ドナルド・クヌースはそれをコンピュータープログラムの複雑さの研究に適用しました。
表記が使用された理由を知りたい場合は、読んでください
1892年のPaulBachmannによる「AnalytischeZahlentheorie」
回答
更新：答えを整理してより正確にしようとしています
Big O表記は、成長率に応じて関数を特徴付ける方法です。O順序を表します（1次はn、2次はn-squaredなど）。誤ってこれは、N個の要素が与えられたメソッドランタイム（またはストレージ）の最悪のシナリオになります。順序が大きいほど、メソッドのパフォーマンスは最悪になります。
たとえば、配列内のレコードを検索するのはO（1）です（ハッシュテーブルの実装もそうだと思います）。要素などを追加する前にリストの最後に到達する必要があるため、リンクリストの最後に値を追加するとO（N）になります。
この回答はより少し正しいはずです。私の最初の試み：）
コメント
- -1これは単なる古い誤りであり、尋ねられたものとは別の質問に答えたためです。問題は、”ではなく、” O “という文字が使用される理由です。表記は機能しますか？”。 ‘ Big-ohの動作についても間違っています…配列をループするのはO（n）です。ここで、nは配列のサイズであり、O（1）ではありません。 。この表記は、アルゴリズムの”サイクル”とは関係ありません… it ‘アルゴリズムの実行時間の上限の測定。
- ここで議論する必要はありませんが、’は私が意味したことの一種です。ランタイムとはどういう意味ですか？実行時間は、マシンで何を処理する必要があるかによって決まります。 ここではサイクルをたっぷり使っていると思います。 サイクルごとに、私は反復スルーまたはそのようなことを言うべきだったと思います。 あなたはしかし上限について正しいです、それは平均を決定しません。 したがって、私はダウングレードを受け入れます。