ビッグ・オー記法と対数

対数というのは、指数をいろいろな人が掘り下げるために主役(?)のように仕立てたもので、「指数=log^基数(底) 真数」という式で表現できるものです。
例えば、「6=log^4 4096」なら4を4096にするために必要な指数は、6だ、と言えます。
ここで質問ですがビッグ・オー記法で表記された式「O(log n)」は、logがあるので恐らく対数と関係があるのだと思います。
カッコの外にあるOは、係数を何らかの事情で省いたことを示すものということもわかります。しかし「指数=log^基数(底) 真数」という形ではないのでいまいち「O(log n)」
という式が理解できません。Oは、係数を省いていることを示しているのですが、この場合は指数を省いているということであっているのでしょうか。
またカッコ内には、logのほかnしかありません。このnは、基数ですか。それとも真数でしょうか。

No.3 ベストアンサー 回答者： rinkun 回答日時： 2017/08/24 08:58

対数logの底は省略されることもあり、分野によって下記に様な意味で使われます。

・常用対数(底は10) 工業分野で良く使われ、区別のためにLogと書かれることも多い
・自然対数(底はe) 数学で良く使われ、工業分野では区別のためにlnと記される
・二進対数(底は2) 情報理論で良く使われる

ビッグ・オー記法だと分野的には二進対数ですが、ANo.2に書かれているように定数分の違いしかないので対数の底は何でも良いのです。

No.4 回答者： NemurinekoNya 回答日時： 2017/08/26 15:28

x→aのとき、f(x)とg(x)がともに限りなく0（または±∞）に近づくとする。

そして、
x→aのとき、f(x)/g(x)の極限が0でない有限な値をもつとき、
　　f(x)=O(g(x))
と書く。

いちおう、上のものがランダウのビッグオー（O）の定義です。

たとえば、
x→0のとき、x→0でsinx→0で、かつ、
　　sinx/x→1 (x→0)
だから、xとsinxは同位の無限小といい、
　　sinx=O(x)
と書く。

この質問だけですと、このO(log n)という記号が何を意味しているのかよくわからないので、次の記事などを読んでみては如何ですか。
http://mathtrain.jp/landausymbol

なお、ランダウのオー記号には、スモールオー（o）とビッグオー（O）がありますので、この両者を混同しないように。
ネットにあるランダウのオー記号の説明を読むときは、ビッグオーOを使っているのか、スモールオーoを使っているのか、このことを留意して読んでください。

No.2 回答者： rabbit_cat 回答日時： 2017/08/24 01:03

オーダー表示では、言われるとおり、（イメージ的には）、係数を省いているわけです。

で、対数の底の変換公式というのを思い出してみれば、対数の底がなんであろうと定数倍しか変わらないので、オーダー表示で省かれてしまいますから、
オーダー表示を使っている時点で、対数の底は、なんでもいいことになります。

No.1 回答者： springside 回答日時： 2017/08/23 21:02

まず、Oは、係数を省いてることを示している記号ではなく、"Order"の頭文字です。

（日本語で言うと「等級」というイメージが近い。「その程度の大きさの量」という感じ）

で、「log n」ですが、底を書かない（省略している）場合、通常は、その対数の底はe(≒2.71828…)です。
当然、nは真数です。

eについて、詳しくは、→https://ja.wikipedia.org/wiki/%E3%83%8D%E3%82%A4 …