1

So I am trying to understand the data types and Big O notation of some functions for a BST and Hashing.

So first off, how are BSTs and Hashing stored? Are BSTs usually arrays, or are they linked lists because they have to point to their left and right leaves? What about Hashing? I've had the most trouble finding clear information regarding Hashing in terms of computation-based searching. I understand that Hashing is best implemented with an array of chains. Is this for faster searching or to decrease overhead on creating the allocated data type?

This following question might be just bad interpretation on my part, but what makes a traversal function different from a search function in BSTs, Hashing, and STL containers? Is traversal Big O(N) for BSTS because you're actually visiting each node/data member, whereas search() can reduce its time by eliminating half the searching field?

And somewhat related, why is it that in the STL, list.insert() and list.erase() have a Big O(1) whereas the vector and deque counterparts are O(N)?

Lastly, why would a vector.push_back() be O(N)? I thought the function could be done something along the lines of this like O(1), but I've come across text saying it is O(N):

vector<int> vic(2,3);
vector<int>::const iterator IT = vic.end();

//wanna insert 4 to the end using push_back

IT++;
(*IT) = 4;

hopefully this works. I'm a bit tired but I would love any explanations why something similar to that wouldn't be efficient or plausible. Thanks

4

2 に答える 2

1

BST（Ordered Binary Trees）は、親ノードが2つの子を指し、次に最大2つの子を指す一連のノードです。トラバーサルはすべてのノードを訪問するため、O（n）時間でトラバースされます。ルックアップにはO（log n）時間がかかります。内部的には既存のノードの束を必要としないため、挿入にはO（1）時間がかかります。いくつかのメモリを割り当てて、ポインタを再照準するだけです。:)

ハッシュ（unordered_map）は、ハッシュアルゴリズムを使用して要素をバケットに割り当てます。通常、バケットにはリンクリストが含まれているため、ハッシュの衝突によって同じバケットに複数の要素が含まれることになります。予想どおり、トラバーサルは再びO（n）になります。ルックアップとインサートは償却されますO（1）。償却とは、平均してO（1）を意味しますが、個々の挿入によって再ハッシュ（衝突を最小限に抑えるためのバケットの再配布）が発生する可能性があります。しかし、時間の経過とともに、平均的な複雑さはO（1）になります。ただし、big-O表記は、実際には「定数」の側面を扱っていないことに注意してください。成長の順序のみ。ハッシュアルゴリズムの一定のオーバーヘッドは、一部のデータセットではO（log n）二分木がハッシュよりも優れているほど高くなる可能性があります。それにもかかわらず、ハッシュの利点は、その操作が一定の時間計算量であるということです。

検索関数は（二分木の場合）「順序」の概念を利用します。BSTを介した検索には、順序付けられた配列を介した基本的なバイナリ検索と同じ特性があります。O（log n）の成長。ハッシュは実際には「検索」しません。彼らはバケットを計算し、次に衝突をすばやく実行してターゲットを見つけます。そのため、ルックアップは一定時間です。

挿入と消去については、配列ベースのシーケンスコンテナでは、ターゲットの後に来るすべての要素を右側にバンプする必要があります。C ++ 11の移動セマンティクスはパフォーマンスを向上させることができますが、操作はO（n）のままです。リンクされたシーケンスコンテナ（list、forward_list、trees）の場合、挿入と消去は、内部でいくつかのポインタをいじることを意味します。これは一定時間のプロセスです。

ベクトルの既存の割り当てられた容量を超えるまで、push_back（）はO（1）になります。容量を超えると、新しい割り当てが行われ、より多くの要素を受け入れるのに十分な大きさのコンテナーが生成されます。次に、すべての要素をより大きなメモリ領域に移動する必要があります。これはO（n）プロセスです。Move Semanticsはここでも役立つと思いますが、それでもO（n）になります。ベクトルと文字列は、増大するデータセットにスペースを割り当てるときに、さらなる増大を見越して、必要以上に割り当てるように実装されます。これは効率の保護手段です。これは、通常のpush_back（）が新しい割り当てをトリガーせず、データセット全体をより大きなコンテナーに移動しないことを意味します。しかし、最終的には十分なpush_backsの後、制限に達し、ベクトル '

于 2012-12-11T09:29:54.300 に答える
0

トラバーサルとは、すべてのノードにアクセスすることを指しますが、検索は特定のノードを見つけることだけを目的としているため、直感はそこにあります。N個のノードにアクセスする必要があるため、O（N）の複雑さ。

std::vector::insertは中央に挿入するためのものであり、挿入される要素、つまりO（N）のためのスペースを確保するために、後続のすべての要素を1つのスロットでコピーする必要があります。リンクリストにはこの問題がないため、O（1）です。の同様のロジックerase。dequeプロパティはに似ていますvector

std :: vector :: push_backはO（1）操作であり、ほとんどの場合、容量を超えて再割り当て+コピーが必要な場合にのみ逸脱します。

于 2012-12-11T08:58:19.033 に答える