5

通常、深さ優先探索を使用すると、時間がO(n)かかります。ただし、最初に最小要素を見つけてからsuccessor()メソッドn時間を呼び出すと、時間計算量はどのくらいになりますか？

O(n log n)後継者がいるからかもしれO(log n)ませんが、そうではないようです。誰かがここで詳細な分析を提供できますか（おそらくいくつかの限界分析を含みます）？

4

2 に答える 2

8

親ポインタが各ノードに存在する場合、後続メソッドをn回呼び出すには、O（n）時間がかかります。これを確認するには、ツリーの各エッジが、すべての後続の呼び出しを組み合わせて、最大2回（親から子に1回、子から親に1回）アクセスされることを確認します。したがって、すべての後続コールがアクセスするエッジの総数は最大2nです。したがって、実行時間はO（n）です。

これで、親ポインターが存在しない場合、すべての呼び出しでルートから開始し、O（log n）ノードを移動して後続要素を検索する必要があります（ツリーのバランスが取れている場合）。したがって、複雑さはO（n log n）になります。

于 2012-09-16T20:20:33.780 に答える
0

正式な議論ではありませんが、O（n）についてはかなり説得力のある議論です。

後続関数は、常に開始ノードから後続ノードまでの最短パスを取ります。下降するか上昇するかのどちらかですが、一度実行を開始すると、もう一方に変更することはできません。したがって、最短経路をたどる必要があります。

後続関数は、深さ優先法と同じ出力を生成する必要があるため、同じ順序で同じノードにアクセスする必要があります（つまり、出力されたノードを通過する必要はありませんが、通過する必要はありません）。 。

また、深さ優先法は、出力された各ノード間の最短パスを常に使用します（各ステップで、両方ではなく、下または上に移動します）。

したがって、各メソッドはまったく同じパスをたどり、実際には同等です。

于 2012-09-16T14:23:28.073 に答える