その理由は次のとおりです。
アルゴリズム A の実行時間は少なくとも O(n²)
無意味ですか？
挿入ソート アルゴリズムの実行時間は最大で O(n²) です
それが正しいか？
ネットで調べてみましたが、うまく説明できませんでした。
別の質問があります:
線形関数 a⋅n+b は O(n) であり、O(n²) であることも知っています。それもO(n³)ですか？
17191 次
10 に答える
15
T(n)T(n)
: アルゴリズム A の実行時間。ステートメントの上限と下限だけを気にします。T(n) >= O(n^2)
Upper bound: なぜなら、
Lower bound: AssumeT(n) >= O(n^2)の上限に関する情報がないため、ステートメント: 、しかし、Ex:よりも「小さい」ものであれば何でもよいので、あまりにも下限についての結論はありませんT(n)f(n) = O(n^2)T(n) >= f(n)f(n)n^2constant, n,...T(n)
=> 発言は無意味
于 2013-03-16T04:34:07.563 に答える
8
1つの理由は、上限のない下限はあまり役に立たないということかもしれません。「少なくとも」とは、通常の場合は指数関数的である可能性があることを意味します。上限がわからない場合は、宇宙が終了する前にプログラムが終了するかどうかがわからないため、実際のアプリケーションでアルゴリズムを使用できない可能性があります。
適切に使用された場合のBigO表記は、上限を示します。したがって、下限を大きなOとして指定すると、表記が乱用されます。
「無意味」というのは強い言葉です。たとえそれが十分でなくても、それは確かに有用な情報です。あなたの質問にもう少し文脈があれば、あなたはより良い助けを得ることができます。
于 2013-03-04T06:56:22.663 に答える
1
線形関数 an+b は O(n) であり、O(n^2) であることも知っています。それも O(n^3) ですか？
はい、そうです。big-O 表記は、関数の集合全体を表します。ただし、関数をできるだけ厳密に特徴付けるために使用する必要があります。である、または偶数であるというのは本当ですf(n) = an+bが、より正確には、 であると言う方が正確です。O(n^2)O(n^3)f(n) = O(n)
于 2014-01-06T23:46:53.283 に答える
0
無意味ではありません。たとえば、正確なアルゴリズムがわからない場合に使用できますが、O(n^2) 操作が必要になることは確かにわかっています。
たとえば、並べ替えアルゴリズムについては知らなくても、配列を並べ替えるには少なくともすべての要素を調べる必要があることを理解している場合、「配列の並べ替えは少なくとも O(n) である」と言うことができます。
于 2013-03-04T09:37:51.433 に答える
0
最良の場合の動作速度は誰も気にしないため、最悪の場合が重要です。通常、人々は最悪の場合にどれくらいかかるかを知りたいと思っています。
于 2013-03-04T15:54:24.837 に答える
0
O 表記法、つまり、次のことを意味します: f(x) は集合 O(g(x)) に属します f(x) < C * g(x) の場合、すべての C について (これらは実数です)
つまり、アルゴリズムは二次関数を超えて成長しません
于 2013-03-04T07:26:13.950 に答える
-3
「アルゴリズム A の実行時間は少なくとも O(n2) です」 は、「アルゴリズム A の実行時間は Big Omega(n2) です」 に相当するので、無意味ではありません。
于 2013-03-04T07:16:50.343 に答える