0

アルゴリズムの複雑さに関するテキストを読んでいますが（後でアルゴリズムコースを受講する予定です）、次のことを理解していません。

順序付けされていないリストでアイテムを検索する必要があるとすると、それを見つけるために必要なステップ数は、そのリストのアイテムの数に比例します。10アイテムのリストでそれを見つけるには、10ステップかかる可能性があり、100000アイテムのリストに対して同じことを行うと、100000ステップかかる可能性があります。したがって、アルゴリズムの複雑さは線形であり、「O（n）」で表されます。

さて、このテキスト[1]は、リストを社会保障番号などのプロパティで並べ替えると、アイテムを見つけるためのアルゴリズムの複雑さがO（log n）に減り、はるかに高速になります。コース。これで、Bツリーの場合にこれが発生していることがわかりますが、これはリストにどのように適用されますか？英語は私の母国語ではないので、私はテキストを誤解しますか？

[1] http://msdn.microsoft.com/en-us/library/ms379571.aspx

4

2 に答える 2

0

これは、ランダムにアクセス可能なすべてのコンテナで機能します。リストの場合、最初に中央の要素に移動します。それがターゲットではないと仮定すると、順序は、ターゲットが上位サブリストに含まれるか下位サブリストに含まれるかを示します。これは本質的にバイナリ検索になり、bツリーを検索するのと同じです。

于 2011-05-27T16:05:25.077 に答える
0

二分探索、ターゲットが高い場合は右側にある必要があり、低い場合は中央の数値など、中央をチェックします。リストを2つに分割するたびに、O（log n）が残ります。

于 2011-05-27T16:05:38.577 に答える