本の定義は言った
「Big-Oh」表記
f(n) と g(n) を、非負の整数を実数にマッピングする関数とします。実定数 c > 0 と実定数 n0 ≥ 1 が存在する場合、f(n) は O(g(n)) であると言います。
f(n) ≤cg(n), for n ≥ n0.
数式と定義で使用される用語を理解できませんでした。だれか平易な英語で説明できますか。
10517 次
3 に答える
3
基本的に、はf(n)の最悪のシナリオに比例します。O(g(n))g(n)f(x)
たとえば、二分探索はO(log n)(またはO(ln n)同等の ) です。なんで？
(バイナリ検索は次のように機能します: 中間の要素を取得し、ターゲットと比較します。それがターゲットの場合は完了です。ターゲットよりも大きい場合は、リストの後半を捨てて前半を繰り返します。ターゲットより小さい場合は、前半を破棄して後半で検索を繰り返します。)
3 要素の長さのリストで何かを見つけるには、1 つの操作が必要だからです。要素数が 7 の場合は 2 操作。15 要素の長さの場合は 3。したがって、要素の数が のn場合(2^x - 1)、x操作の数はxです。nそれをひっくり返すと、要素の数に対して操作の数は と言えますlog_2 n。そして、各操作が 2 秒続くとします (たとえば、手動で比較しているとします)。検索に最悪の時間はlog_2 n * 2 seconds. log_2 nのように書き直すことができるln n / ln 2ので、式は次のようになります。
worst search time(n) = (ln n / ln 2) * 2 seconds
= (2 seconds / ln 2) * ln n
さて、2 seconds / ln 2定数です。と呼びましょうc。「n要素の検索時間」と呼びましょうf(n)。ln nとして呼び出しましょうg(n)。
前に、if について述べn = 3ましg(3) <= c * ln 3た (c * ln 3は最悪の検索時間であるため、実際の検索時間は常にそれ以下ですが、最初の試行で常に見つけることができます)。もしn = 7、g(7) <= c * ln 7; 等
ちょっとしたことn0は、小さなものについて計算する複雑さは、規則からの逸脱、異常、例外である可能性があるという単なる警備員であり、n十分に大きなデータ (つまりn >= n0) を使用すると、規則は明らかになり、違反しなくなります。この場合、ルールは最初からほとんど機能しますが、アルゴリズムによっては、小さな数の計算を妨げる余分なコストがかかる場合があります。
于 2013-07-31T05:45:34.620 に答える
1
「平易な英語」への翻訳: f(n) は、入力として正の数またはゼロを取り、出力として実数を与える g(n) 関数であると想像してください (虚数ではありません)。
Big-Oh を使用すると、2 つの関数を比較して、一方が他方に制限されているかどうかを確認できます。たとえば、指数関数f(n)は線形関数 によって制限されないg(n)ため、 でf(n)はありませんO(g(n))。
f(n)次のことがO(g(n))可能であれば、それであると言えますf(n) ≤ c * g(n) for n ≥ n0。cとを差し込んで方程式を解く方法がある場合n0、f(n)は ですO(g(n))。
たとえば (上記と同じ)、 let f(n) = 2^n, g(n) = n. 次は解ける2^n ≤ c * n for n ≥ n0か? 答えはノーだ。にどのような値が差し込まれても、無限大に近づくにつれてc常に左辺が右辺よりも大きくなります。nすべての値について、左辺を右辺よりも小さくする方法はありませんn ≥ n0。
一方、 の場合f(n) = 2n, g(n) = n、条件は2n ≤ c * n for n ≥ n0です。これは解決可能です: c = 2, n0 = 0.
于 2013-07-31T05:30:11.927 に答える
0
f(n) と g(n) を、非負の整数を実数にマッピングする関数とします。
f (n)とg(n)を、ie domainの値nが 0 または正の整数である関数とすると、これらの値に対するf(n)とg(n)の値はn実数である可能性があります。
次のような実定数 c > 0 と実定数 n0 ≥ 1 がある場合、f(n) は O(g(n)) であると言います。
n ≥ n0 の場合、f(n) ≤cg(n)。
f(n) = O(g(n))正の定数が存在しc、すべてのn >= n0n0に対して
0 <= f(n) <= cg(n)となる場合。実際には、が漸近的に より小さいか等しいことを意味します。f(n)g(n)
たとえば、f(n) = 3 * n^2 + 5を考えてみましょう。c = 4とn0 = 2を選択することで、 f(n)がO(n^2)であることを示すことができます。これは、すべての値がより大きいためです。n2
3 * n^2 + 5 <= 4 * n^2
f(n)はO(n )ではありません。なぜなら、どのような定数cと値n0を選択しても、3 * n^2 + 5 が より大きいという値を常に見つけることができるからnです。n0c * n
于 2013-07-31T05:19:48.677 に答える