language-agnostic - Big-O 記法に代わるものはありますか?

Question

皆さん、こんにちは。

ハッシュテーブルには O(1) ルックアップ (キーがある場合) があると言いますが、リンクされたリストには次のノードの O(1) ルックアップがあります (現在のノードへの参照がある場合)。

ただし、Big-O 表記法がどのように機能するかにより、アルゴリズムxのコストとアルゴリズムx + mのコストを表現 (または微分) するのにあまり役に立ちません。

たとえば、ハッシュテーブルのルックアップとリンクされたリストのルックアップの両方に O(1) というラベルを付けたとしても、これら 2 つの O(1) は非常に異なるステップ数になります。

リンクされたリストのルックアップはxステップ数に固定されています。ただし、ハッシュテーブルのルックアップはvariable です。ハッシュテーブルのルックアップのコストはハッシュ関数のコストに依存するため、ハッシュテーブルのルックアップに必要なステップ数はx + mです。

1. ここで、xは定数です

2. mは未知の変数値です

つまり、両方の操作を O(1) と呼んでも、ハッシュテーブルのルックアップのコストは、リンクされたリストのルックアップのコストよりもはるかに高くなります。

Big-O 表記は、具体的には入力データ コレクションのサイズに関するものです。これには利点がありますが、 n以外のすべての変数を 1 に折りたたんで正規化するとわかるように、欠点もあります。その中に m 変数 (ハッシュ関数) はもう見えません。

Big-O 表記法以外に、x操作を意味する固定コスト O(1 )とx + m ( m、ハッシュ関数) 操作数?

Answer 1

正確に1つの操作を意味するリテラルO（1）

そうでないことを除いて。大きなO表記は、入力に関連する複雑さの相対的な比較に関係しています。アルゴリズムが入力のサイズに完全に関係なく一定のステップ数をとる場合、正確なステップ数は重要ではありません。

O（n）の（非公式の）定義を見てください。

kつまり、それぞれnの関数fが関数よりも小さいという特定のことがありますg。

上記の場合、ハッシュテーブルルックアップとリンクリストルックアップは、になりf、gはになりますg(n) = 1。いずれの場合も、それを見つけることができkますf(n) <= g(n) * k。

現在、これkを修正する必要はありません。プラットフォーム、実装、特定のハードウェアによって異なる可能性があります。唯一の興味深い点は、それが存在することです。そのため、ハッシュテーブルルックアップとリンクリストノードルックアップはどちらもO（1）です。どちらも、入力に関係なく、一定の複雑さを持っています。そして、アルゴリズムを評価するとき、それは物理的なステップではなく、興味深いものです。

特にハッシュテーブルルックアップについて

はい、ハッシュ関数はさまざまな量の操作を実行します（実装によって異なります）。ただし、入力のサイズに応じて操作量を変える必要はありません。Big O-Nationは、具体的には入力データコレクションのサイズに関するものです。ハッシュ関数は単一の要素を取ります。アルゴリズムの評価では、特定の関数が10、20、50、または100の操作を行うかどうかは関係ありません。操作の数が入力サイズとともに増加しない場合、それはO（1）です。これは大きなO-Notationの目的ではないため、大きなO-Notationでこれを区別する方法はありません。

Answer 2

"~" には定数係数が含まれます - bachmann 関数のファミリーを参照してください

Answer 3

問題は、「操作の数」がコンテキストに大きく依存することです。実際、それがbig-O表記法が発明された理由です。これは、多数のコンピューターのモデリングでかなりうまく機能しているようです。

さらに、プログラマーが「操作」の数をどのように処理するかは、実際にかかる時間（たとえば、既にキャッシュにあるかどうか）やハードウェアが実際にかかるステップ数（プロセッサは-正確に-何をするか）を意味しません。マイクロオペレーションがありますか？）またはプロセッサに指示される操作の数（コンパイラはあなたのために何をしていますか？）。そして、有用であるほど抽象的である正確な概念を定義しようとするときでさえ、それらはすべて懸念事項です。

それで。今のところ、それはBig-O対「操作」です-その時点であなたとあなたの同僚にとって「操作」が意味するものは何でも。