-4

ソートされていないセット S で O(n log n) 時間で 2 つの異なる数値 a と b を見つけて |ab| を得るにはどうすればよいですか? 可能なすべてのペアの中で最小ですか?

4

1 に答える 1

1

まず、O(n log n) であるクイックソートなどを使用してリストをソートします。

次に、各数値と次の数値の間の間隔を測定し、見た最小の間隔を追跡しながら、リストを 1 回通過します。それが O(n) です。

O(n) + O(n log n) = O(n log n)

于 2013-03-29T04:02:29.180 に答える