問題タブ [lower-bound]

上限と下限の両方の漸近境界の例がいくつかありますが、それぞれの主項または n 項を考慮している理由がわかりません。誰か説明してくれませんか？

漸近上限:

12n^3 + 8n + 20 = O(n^3)

12n^3 + 8n + 20 = O(n^5) [ 12n^5 であるべきだと思う]

漸近下限:

12n^3 + 8n + 20 = オメガ(n^3)

12n^3 + 8n + 20 = オメガ(n)

定義を読みましたが、なぜ下限で変化し、なぜ上限で変化するのか理解できません。

std::lower_bound( )の最初のステップとして簡単な比較がないのはなぜですか?

最初のステップでstd::lower_boundイテレータがリスト内から中央の位置に変更itさfirstれると、次のようになります。

その後、アルゴリズムはその center-itと givenの比較を開始しvalueます。

しかし、些細なケースは、再配置する前の最初のステップとして 1 つの比較を行うことitです。

std::lower_bound非常に長いリストがあり、現在の形で が実現するまで待つ必要があると想像してください。これvalue < *firstは本当です。確かにO( log_2( last - first ) )ですが、そのような場合はO(1)に 1 行だけ追加される可能性があります。

私はweak_ptrのソートされたベクトルを検索するためにlower_bound()を使用しています

はどこsaにありshared_ptr<A>、クラスAにはプライベートstring IDメソッドとパブリック メソッドがありgetIDます。findA呼び出すと、セグメンテーション違反が発生しgetIDます。が原因だと思いますがlock()、これは empty を再実行しますshared_ptr。

どうすれば修正できますか？

Pythonで提供された値の次の最小値を取得するにはどうすればよいですか? そのための組み込み関数はありますか？

3 の次に小さいもの、または 2 の次に大きいものを見つけるにはどうすればよいですか? 期待される結果は、それぞれ 2 と 3 です。

k 個のグループに含まれる n 個の数値の単一の並べ替えられたリストを生成する時間の下限を指定します。最小の n/k が最初になるようにします。

そのため、私はしばらくこの問題に悩まされていましたが、どうすればいいのか本当にわかりません。決定木を作成する方法は知っていますが、この問題のコンテキストでそれを行う方法がわかりません。私は必ずしも問題を理解しているわけではありませんが、人々にとって解決できるほど明確であるように思えます。正しい方向または明確化のポイントは非常に高く評価されます。

アルゴリズムの上限と下限をどのように証明できますか?

これまで、アルゴリズムの上限と下限の両方を、すべての入力を考慮して、f(n) [上限] よりも悪くはならず、g(n) よりも良くないことを示すことによって示す必要があると考えていました。 [下限]。

私の講師は、上限については[すべての入力を考慮して]一般的に証明する必要があるが、下限については例で十分であると言いました。

これは本当に私を混乱させました。誰かが彼が何を意味したかを明確にすることができますか?

宿題の問題に遭遇しました：

サイズの整数の任意の配列で最大要素を見つける最適なアルゴリズムの最良の場合の実行時間の漸近的にタイトな上限はどれですかn

1. O(ログ n)
2. O(n ² )
3. の上）
4. O(1)
5. O(n log n)

私の理解に基づくと、これは O(n) です。これは最良のケースであっても、結果を取得するために arr をスキャンする必要があるためです。私を修正してください

アルゴリズムの場合、境界は最良/最悪のケースにどのように関連していますか? 最悪のケースは上限と同義であり、最良のケースは下限と同義ですか? または、少なくとも一方を他方から派生させることができますか? それとも、まったく関係がないのでしょうか?