1

この宿題の質問があります

「ジェームズは、O（（log n）^ 0.5）をとる最大ヒープ（ExtractMax）からの抽出の実装に成功したと主張しています。

ジェームズが間違っている理由を説明する

最大ヒープから抽出するにはO（log n）が必要ですが、Jamesが間違っていることをどのように証明できますか？

4

2 に答える 2

2

ここでわかるように、ヒープの構築は O(n) で実行できます。最大値の抽出が O((log n)^0.5) で実行できる場合、最大の要素を繰り返し抽出することで、セット全体を n * O((log n)^0.5) で並べ替えることができます。ただし、ソートの下限が n*logn であるため、これは不可能です。

したがって、ジェームズのものは存在しません。

于 2012-06-02T22:34:33.383 に答える
1

抽出の問題をソートの問題に変換する@Duhのソリューションは、実際には非常に創造的です。並べ替えが O(n * log n) であることの証明を見つけるのはそれほど難しくありません。アルゴリズムの研究では、ある問題を別の問題に変換することは非常に一般的です (たとえば、すべての NP 完全問題は次の変換です)。それが NP-Complete であることを証明する方法です)。そうは言っても、もっと簡単な解決策があると思います。

質問で直接述べました：バイナリヒープからの抽出はO（log n）です。なぜO(log n)なのか考えてみてください。バイナリヒープの構造は何ですか? バイナリ ヒープから抽出するには、どのようなアクションが必要ですか? 最悪のケースが log n 操作になるのはなぜですか? これらの制限は、実装によってまったく影響を受けますか?

ここで、James の主張には 2 つの部分があることを思い出してください。

  1. 彼は O((log n)^0.5) で抽出できます
  2. 彼はバイナリヒープを使用しています。

バイナリ ヒープについて知っていることを考えると、これらの主張は両方とも正しいのでしょうか? なぜですか、そうでないのですか？矛盾はありますか？もしそうなら、なぜ矛盾があるのですか？最後に、これが James にとって何を意味するかを考えてください。

于 2012-06-03T10:06:40.093 に答える