問題タブ [big-o]

big-Oが紹介されたクラスは、かなり簡単だと思って欠席しました。それでも、nが非常に小さくなると、先生はO（n）が関数から外れることについて何か言ったようです。私は本のどこにもこれを見つけることができませんでした。誰かが私を教えてもらえますか？O（n）の調査は、それが重要である場合、ソートアルゴリズムのコンテキストで行われました。

ありがとうジーン

編集：それが照らしている助けてくれてありがとう。フォローアップの質問があります。nがO（n）に対して小さすぎる点を理解するための比較的簡単な数学的方法はありますか？

関連する質問

O（1 / n）アルゴリズムはありますか？
Θ（n）とO（n）の違いは何ですか？

次の手順 (説明が続きます) は、非常に小さなリストでは問題なく機能しますが、リストに含まれるアイテムの数が多い (1/2 百万) 場合、アプリケーションは「応答なし」状態になり、完了するまでに約 2.5 分かかります (非常に悪い)時間）。少なくとも (最終的には) 1 億項目のリストを処理する必要があるアプリケーションを追加する可能性があります。

問題のある手順のコードは次のとおりです。

L は long 値のリストです。_subLists は、各値が L からの値のリストであるソートされたリストであり、いくつかの違いの算術級数シリーズを開始します (関係ありません)。その値に関連付けられたキーは、値に含まれる系列の長さです。

例：

L = {1,2,3,5,6,7,18,20,21} _subLists = {2,<20>} {3,<1,5>}

この手順は、単純に L から算術級数級数を削除します。

Dictionary<K,V>.NETコレクションクラス（など）のメソッドの漸近的な複雑さ（big-Oおよびその他）に関するリソースはありますList<T>か？

C5ライブラリのドキュメントにそれに関する情報が含まれていることは知っていますが（例）、標準の.NETコレクションにも興味があります...（そしてPowerCollectionsの情報もいいでしょう）。

どちらに時間がかかりますか？

バイナリ検索ツリーに格納されているすべてのアイテムを並べ替えられた順序で印刷するか、ハッシュテーブルに格納されているすべてのアイテムを並べ替えられた順序で印刷します。

ハッシュテーブルが正しくソートされないため、ハッシュテーブルのアイテムをソートされた順序で出力するのに時間がかかりますか？そしてBSTは？

空の二分探索木 n^2 に N 個の項目を挿入する最悪のケースが big-O になるのはなぜですか? 残高チェックはありません。

n単語と頻度のペアの配列が与えられた場合:

ここで、 は単語、は整数の周波数、周波数の合計、wifi∑fi = m

任意の単語を選択する確率がその頻度に比例するように、擬似乱数ジェネレータ (pRNG) を使用してp単語を選択したいと考えています。wj0, wj1, ..., wjp-1

(これは置換を伴う選択であるため、毎回同じ単語が選択される可能性があることに注意してください)。

これまでに 3 つのアルゴリズムを考え出しました。

1. サイズ の配列を作成しm、最初のエントリが、次のエントリが、というように、最後のエントリがになるように入力します。f0w0f1w1fp-1wp-1

   次に、pRNG を使用pして範囲内のインデックスを選択し0...m-1、それらのインデックスに格納されている単語を報告します。n よりもはるかに大きくなる可能性があるため、
   これには手間がかかります。O(n + m + p)m

2. 入力配列を 1 回ステップ実行し、計算します。

   を計算した後、pRNG を使用して のそれぞれの範囲内の数値を生成し、 for を選択します(場合によっては の現在の値を置き換えます) 。 これには作業が必要です。mixk0...mi-1k0...p-1wiwjkwjkxk < fi
O(n + np)

3. アルゴリズム 2 のように計算し、n 個の単語-頻度-部分和のトリプルで次の配列を生成します。mi次に、各 k in0...p-1について、pRNG を使用して範囲内の数値を生成し、トリプルの配列でバイナリ検索を実行してstを見つけ、 forを選択します。 これには作業が必要です。xk0...m-1imi-fi ≤ xk < miwiwjk
O(n + p log n)

私の質問は次のとおりです。これに使用できるより効率的なアルゴリズムはありますか、それともこれほど優れていますか?

これがシナリオです。

整数の配列「A」が与えられます。配列のサイズは固定されていません。私が書くことになっている関数は、数個の整数の配列で一度呼び出されるかもしれませんが、別の時には数千の整数を含むかもしれません。さらに、各整数が同じ桁数である必要はありません。

結果の配列が辞書式に並べられた整数を持つように、配列内の数値を「ソート」することになっています（つまり、文字列表現に基づいてソートされます。ここで「123」は123の文字列表現です）。出力には、文字列の同等物ではなく、整数のみを含める必要があることに注意してください。

例:入力が次の場合:

[ 12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000 ]

次に、出力は次のようになります。

[ 1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654 ]

私の最初のアプローチ：各整数をその文字列形式に変換し、その右側にゼロを追加して、すべての整数に同じ桁数が含まれるようにしました（これは、追跡などが含まれ、ソリューションが非常に非効率になるため、面倒な手順でした）。基数ソート。最後に、パディングされたゼロを削除し、文字列を整数に戻して、結果の配列に入れました。これは非常に非効率的なソリューションでした。

私は、解決策にはパディングなどは必要なく、結果を得るために何らかの方法で数値を処理する必要がある単純な解決策があると信じるようになりました。

あなたが考えることができる空間的に最も効率的な解決策は何ですか? 時間的に？

コードを提供する場合は、Java または疑似コードをお勧めします。しかし、それがあなたに合わない場合は、そのような言語で問題ありません。

アルゴリズムを並列化することで、線形速度の向上以上の効果が得られるケースはありますか?

配列の合計値を計算するためのアルゴリズムを見つける方法は??

こんな感じですか？

そして、O-Notationを使用して、アルゴリズムの実行時間とどのように関連付けることができますか

これは昨年の試験であり、試験の改訂を行う必要があります。

質問
n個の整数値を保持する配列A[]が与えられ
ます1.配列内のすべての値の合計を計算するためのアルゴリズムを与えます2.アルゴリズム
の実行時間の最も単純で最良のO表記を見つけます。