search - BST の最悪の時間の複雑さ (postorder をたどる)

Question

Nノードの二分探索木でのポストオーダー トラバーサルの時間計算量を考えてみましょう。一般的なケースでは、すべてのノードにアクセスする必要があることはわかっていますがO(N)、BST がリストの場合、最悪の場合の複雑さはどのくらいですか? O(N^2)ノードをトラバースNして最後に到達し、Nノードを最初に戻すため、が必要だと思います。ということN*N = N^2で、そうだと思いますO(N^2)。そうですか？

Answer 1

あなたの「最悪のケース」のシナリオ (率直に言って、私には理解できません) では、N * N = O(N^2) ではなく、N + N = O(N) です。