-1

以下のテキストは、二項キューの記事からのものです。

左翼ヒープとスキュー ヒープの両方が、操作ごとに O(log n) 時間で効果的にマージ、挿入、および delete_min をサポートしますが、バイナリ ヒープは操作ごとに一定の平均時間で挿入をサポートすることがわかっているため、改善の余地があります。二項キューは、操作ごとに O(log n) の最悪の場合の時間で 3 つの操作すべてをサポートしますが、挿入には平均して一定の時間がかかります。

上記のテキストで、操作ごとの一定の平均時間とは、著者が何を意味するのですか? また、二項キューの挿入とはどのように異なり、平均して一定の時間がかかりますか?

操作ごとの一定の平均時間と一定の平均時間の違いは何ですか?

4

1 に答える 1

0

操作ごとの一定の平均時間と平均の一定時間の違いは何ですか？

違いはありません。著者は、一方では左利きヒープとスキューヒープを対比し、もう一方ではバイナリヒープを対比して、二項ヒープには、左利きヒープとスキューヒープにはないバイナリヒープ（予想されるO（1）挿入）のいくつかの利点があることを示しています（償却済みのO（1）インサートのみがあります）。

于 2011-09-19T13:29:00.993 に答える