問題タブ [big-o]

2 ^ n + 6n ^ 2 + 3n

最高位の項を使用したO（2 ^ n）だと思いますが、これを証明するための正式なアプローチは何ですか？

私は明日非常に重要なインタビューのために勉強していますが、私が非常に問題を抱えていることが1つあります。それは、ソートアルゴリズムとBigOの効率です。

知っておくべき重要な数字は何ですか？最高、最悪、または平均の効率？

基本的なデータ構造の漸近的分析を 1 か所 (テーブルかもしれませんが、そうである必要はありません) にうまく整理されている場所を知っている人はいますか? データ構造と、検索およびソートのアルゴリズムについての理解を新たにしたいと思います。だから私は最高の平均を探しています。そして最悪のシナリオ。

STLが含まれていても問題ありません。

誰かが私にこれを少し説明できるかどうか疑問に思っていました. 積分法または切り捨て限定法を使用してシータ関数の推定値を計算する方法を知りたいです。

たとえば、次のように計算します。

∑<sub>i=1..ni⋅sqrt(i)+1

アルゴリズム/データ構造を検討するときはいつでも、log（N）部分を定数に置き換える傾向があります。ああ、log（N）が発散することは知っていますが、実際のアプリケーションでは重要ですか？

log（infinity）<100すべての実用的な目的。

私はこれが当てはまらない実世界の例に本当に興味があります。

明確にするために：

• 私はO（f（N））を理解しています
• 漸近的な振る舞いが実際のパフォーマンスの定数よりも重要である実世界の例に興味があります。
• log（N）を定数で置き換えることができる場合でも、O（N log N）の定数で置き換えることができます。

この質問は、（a）エンターテインメントと（b）デザインのパフォーマンスについての論争に（再び）遭遇した場合に使用する引数を収集するためのものです。

入力サイズが 100 の場合、アルゴは 0.5 ミリ秒かかります。入力サイズが 500 で、プログラムが O(n lg(n)) の場合、実行にかかる時間はどれくらいですか?

私の本によると、入力サイズが 2 倍になると、n lg(n) は「2 倍より少し長い」時間がかかります。それは本当に私を助けていません。

私が行ってきた方法は、定数乗数を解決することです（本では説明されていないため、有効かどうかはわかりません）：

.5ms = c * 100 * lg(100) => c = .000753

そう

.000753 * 500 * lg(500) = 3.37562ms

それは実行時間を計算する有効な方法ですか?それを把握するためのより良い方法はありますか?

次のフラグメントのビッグ O 実行時間を見つける必要があります。

外側のループが O(n) であることはわかっていますが、内側のループの分析に問題があります。O(log n)だと思います。

昨日のアルゴリズムのテストでこの質問がありましたが、答えがわかりません。約40ポイントの価値があったので、それは私を完全に夢中にさせています. 過去 24 時間以内に解決策を思いつかなかったので、クラスのほとんどが正しく解決していないと思います。

長さ n の任意のバイナリ文字列が与えられた場合、文字列内に等間隔にある 3 つのバイナリ文字列が存在する場合はそれらを見つけます。これを O(n * log(n)) 時間で解くアルゴリズムを書きなさい。

したがって、これらのような文字列には、「等間隔」の 3 つの文字列があります: 11100000、0100100100

編集：これは乱数なので、どの数値でも機能するはずです。私が挙げた例は、「等間隔」の特性を説明するためのものでした。したがって、1001011 は有効な数値です。1、4、および 7 は等間隔です。

二分探索木タイプのデータ構造の場合、Big O表記は通常O（logn）と表記されます。ログに小文字の「l」がある場合、これは自然対数で表される対数基数e（n）を意味しますか？簡単な質問で申し訳ありませんが、私は常に異なる暗黙の対数を区別するのに苦労していました。

以下のコード セグメントの複雑さを分析したところ、 O(n/2)であることがわかりました。しかし、インターネットを検索しているときに、おそらくO(n)であることがわかりました。誰が正しいのか知りたいです。